先帮助差值小的人完成任务

解题思路:

注意事项:

参考代码:

//设某个人拥有a个积木，需要b个积木。a-b就是积木差。a-b>=0表示这个人的积木足够了，a-b<0表示这个人需要等其它人完成后才能拿到足够的积木

//把所有人的积木差求出来，从大到小排序。部分人的a-b>0，则不需要等待，把它们的a-b累加起来叫sum1。

//对于 a-b<0 那部分人应该按 a-b差值的绝对值 排序，先帮助差值小的人完成任务,它完成任务后积木就可以贡献出来给其它人用，直到发现一个无法弥补差值的情况出来。

#include<bits/stdc++.h>

using namespace std;

struct mytype{

   int a,b,c;

} p[10000+1];

bool cmp(mytype p1,mytype p2){

   if(p1.c<p2.c) return true;

   return false;

}

int main()

{

    int m;cin>>m;

    for(int i=1;i<=m;i++){

         int n;cin>>n;

         int sum1=0;

         int cnt=0;

         for(int j=1;j<=n;j++){

             int a,b; cin>>a>>b;  //拥有的积木数 a 和  需要的积木数b。

             if(a-b>=0)  sum1+=a;//积木足够的人可以直接恭喜所有积木

             else { //一开始没拿到足够积木的人先要进数组，再排序

               p[cnt].a=a;

               p[cnt].b=b;

               p[cnt].c=b-a;//b-a是正值

               cnt++;

           }

         }

         sort(p,p+cnt,cmp);

         int j;

         for(j=0;j<cnt;j++){

           if(sum1>=p[j].c) sum1+=p[j].a; //sum1可以补充差值，则这个人完成任务后就贡献了个人积木a。

           else break; //sum1不足以补充差值，直接退出

       }        

         if(j>=cnt) cout<<"YES"<<endl;

         else cout<<"NO"<<endl;

    }

   return 0;

}