算法期末备考-第6练-贪心算法

算法期末备考-第6练

贪心算法

【主要内容】

找硬币

活动安排问题

找硬币

【题目描述】

有四种硬币，分别是25分、10分、5分和1分，给顾客找六角三分。

【题解】

贪心策略是：从大到小找零即可。

 1 #include<cstdio>
 2 
 3 int coin[] = { 25 , 10 , 5 , 1 };
 4 int Num[4] ;
 5 
 6 int main()
 7 {
 8     int n = 63 ;
 9     for( int i = 0 ; n && i < 4 ; i++ ){
10         Num[i] = n / coin[i] ;
11         n %= coin[i] ;
12     }
13     for( int i = 0 ; i < 4 ; i ++ ){
14         printf("Coin %d: %d
",coin[i],Num[i]);
15     }
16     
17     return 0;
18 }
19 /*
20 Coin 25: 2
21 Coin 10: 1
22 Coin 5: 0
23 Coin 1: 3
24 */

找硬币问题

活动安排问题

【题目链接】

https://www.acwing.com/problem/content/910/

【题目描述】

设有n个活动的集合E={1,2,3,…,n}，所有的活动要求使用同一资源，而在同一时间内只有一个活动能使用这一资源，每个活动都有使用这一资源的开始时间si和结束时间fi，且si<fi。目标：要在所给的活动中，找出最大的相容的活动子集合。

【题解】

问题的本质为：最大不相交区间数量

贪心策略：先按右端点从小到大排序，再按左端点从小到大。证明过程在书本

【前置知识】

其实结构体排序不是第一次遇到，在python课上谈及过Lambda按照关键排序，在C#课上也说过Lambda排序或重写CompareTo方法。

其实C++提供了内置的Sort函数。

Sort( a , a + n , cmp )

第一个空填入，数组需要排序的首地址。

第二个空填入，数组需要排序的尾地址。

第三个空填入，传入排序的比较的方式。

我们只需要以这种形式调用，且重写排序的规则即可。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 const int N = 1e5 + 10;
 6 typedef struct Node {
 7     int S , F ; //Start , Finish
 8 }Node ;
 9 Node a[N] ;
10 int n ;
11 int cmp( Node u , Node v ){
12     if( u.F == v.F ){
13         return u.S < v.S ;
14     }
15     return u.F < v.F ;
16 }
17 
18 int main()
19 {
20 
21     scanf("%d",&n);
22     for( int i = 0 ; i < n ; i ++ ) scanf("%d%d",&a[i].S , &a[i].F );
23     sort( a , a + n , cmp );
24 
25 
26     int ans = 1 , End = a[0].F ;
27     for( int i = 1 ; i < n ; i++ ){
28         if( End < a[i].S ){
29             End = a[i].F ;
30             ans ++ ;
31         }
32     }
33     printf("%d
",ans);
34     return 0 ;
35 }

活动安排问题