题目链接：

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

1 #define _CRT_SECURE_NO_WARNINGS 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            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
           
            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 }
           
          
         
        
       
      

 题目链接：

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

1 #define _CRT_SECURE_NO_WARNINGS 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           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
          
           =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 }
          
         
        
       
      

 题目链接：

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

证明如下：

第一件物品 a1 b1

第二件物品 a2 b2

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

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

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

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

1 #define _CRT_SECURE_NO_WARNINGS 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           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 }