hdu 1050+hdu 1789+hdu 3177(贪心）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1050

思路：就是跟hdu2037那题差不多，可不知道为什么一开始我按结束区间的大小排序就wa了，然后改成按开始区间的大小排序就ac了。。。不明白了，还请大牛解释。。。orz

View Code

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<algorithm>
 7 using namespace std;
 8 const int MAXN=200+10;
 9 struct Node{
10     int x,y;
11 }node[MAXN];
12 int n;
13 bool mark[MAXN];
14 
15 int cmp(const Node &p,const Node &q){
16     //按开始区间大小排
17     if(p.x!=q.x){
18         return p.x<q.x;
19     }
20     return p.y<q.y;
21 }
22 
23 int main(){
24     int _case;
25     scanf("%d",&_case);
26     while(_case--){
27         scanf("%d",&n);
28         for(int i=1;i<=n;i++){
29             int x,y;
30             scanf("%d%d",&x,&y);
31             x=(x+1)/2,y=(y+1)/2;
32             if(x>y)swap(x,y);
33             node[i].x=x;
34             node[i].y=y;
35         }
36         sort(node+1,node+n+1,cmp);
37         memset(mark,false,sizeof(mark));
38         int count=0;
39         for(int i=1;i<=n;i++)if(!mark[i]){
40             mark[i]=true;
41             count++;
42             int y=node[i].y;
43             for(int j=i+1;j<=n;j++){
44                 if(!mark[j]&&node[j].x>y){
45                     mark[j]=true;
46                     y=node[j].y;
47                 }
48             }
49         }
50         printf("%d\n",count*10);
51     }
52     return 0;
53 }

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1789

思路：一道贪心好题啊！由于要扣分最少，那么我们可以先按score从大到小排序，然后再按day从小到大排。这样，我们在选的时候，每次都把作业安排在离它的截止期限最近的一天，并把此天标记为已用，若不能安排，则扣分。这样就能保证扣分最少。

View Code

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<algorithm>
 6 using namespace std;
 7 const int MAXN=1000+10;
 8 struct Node{
 9     int day;
10     int score;
11 }node[MAXN];
12 int n;
13 bool mark[MAXN];
14 
15 
16 int cmp(const Node &p,const Node &q){
17     if(p.score!=q.score){
18         return p.score>q.score;
19     }
20     return p.day<q.day;
21 }
22 
23 int main(){
24     int _case;
25     scanf("%d",&_case);
26     while(_case--){
27         scanf("%d",&n);
28         for(int i=1;i<=n;i++)scanf("%d",&node[i].day);
29         for(int i=1;i<=n;i++)scanf("%d",&node[i].score);
30         sort(node+1,node+n+1,cmp);
31         memset(mark,false,sizeof(mark));
32         int ans=0,k=0;
33         for(int i=1;i<=n;i++){
34             for(k=node[i].day;k>=1;k--){
35                 if(!mark[k]){
36                     mark[k]=true;
37                     break;
38                 }
39             }
40             if(k==0)ans+=node[i].score;//说明之前的几天都排满了
41         }
42         printf("%d\n",ans);
43     }
44     return 0;
45 }

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3177

思路：这题很明显是要用贪心来做的，可怎么个贪心是关键，一开始我是尽量放大的，wa了一次，然后就搞了个差值最大，ac了

证明如下：

第一件物品 a1 b1

第二件物品 a2 b2

假设这两件物品的移动体积都不大于洞的体积V

那么将单独比较两个物品的时候会发现 a1+b2为先放第一件物品后放第二件物品的最大瞬时体积

a2+b1为先放第二件物品后放第一件物品的最大瞬时体积

则应该要a1+b2>a2+b1，即a1-b1>a2-b2;

View Code

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<algorithm>
 6 using namespace std;
 7 const int MAXN=1000+10;
 8 struct Node{
 9     int a,b;
10 }node[MAXN];
11 
12 int cmp(const Node &p,const Node &q){
13     return (p.b-p.a)>(q.b-q.a);
14 }
15 
16 int main(){
17     int _case;
18     scanf("%d",&_case);
19     while(_case--){
20         int v,n;
21         scanf("%d%d",&v,&n);
22         for(int i=1;i<=n;i++){
23             scanf("%d%d",&node[i].a,&node[i].b);
24         }
25         sort(node+1,node+n+1,cmp);//尽量先放差值大的
26         bool flag=true;
27         for(int i=1;i<=n;i++){
28             if(v>=node[i].b){
29                 v-=node[i].a;
30             }else {
31                 flag=false;
32                 break;
33             }
34         }
35         if(flag){
36             printf("Yes\n");
37         }else 
38             printf("No\n");
39     }
40     return 0;
41 }