算法提高 盾神与积木游戏

问题描述 　　最近的m天盾神都去幼儿园陪小朋友们玩去了~ 　　每个小朋友都拿到了一些积木，他们各自需要不同数量的积木来拼一些他们想要的东西。但是有的小朋友拿得多，有的小朋友拿得少，有些小朋友需要拿到其他小朋友的积木才能完成他的大作。如果某个小朋友完成了他的作品，那么他就会把自己的作品推倒，而无私地把他的所有积木都奉献出来；但是，如果他还没有完成自己的作品，他是不会把积木让出去的哟~ 　　盾神看到这么和谐的小朋友们感到非常开心，于是想帮助他们所有人都完成他们各自的作品。盾神现在在想，这个理想有没有可能实现呢？于是把这个问题交给了他最信赖的你。 输入格式 　　第一行为一个数m。 　　接下来有m组数据。每一组的第一行为n，表示这天有n个小朋友。接下来的n行每行两个数，分别表示他现在拥有的积木数和他一共需要的积木数。 输出格式 　　输出m行，如果第i天能顺利完成所有作品，输出YES，否则输出NO。 样例输入 2 2 2 2 1 3 3 1 5 3 3 0 4 样例输出 YES NO 数据规模和约定

　　1<=n<=10000，1<=m<=10。

这个题目用贪心算法，将每天积木够完成作品的同学分成一组，组号为E，不够的同学分成一组，组号为I，并将积木不够的同学按照需要的积木-拥有的积木的差值按从小到大排序，E组中公共有sum个积木，将sum个积木依次分给I组中的同学，如果不够输出NO，如果够，sum更新，并继续往下分。

例如

5 2 2 3 2 1 5 2 10 3 9

E组

2 2

3 2

I组（已排序）

1 5

3 9

2 10

sum=2+3=5

I组中第一个小朋友 还需要4个积木而sum>4,所以够 sum更新为6（第一个小朋友用完后他的积木也可以空出来）

第二个小朋友还需要6个积木，而sum=6，所以够，sum更新为9

第三个下小朋友需要8个积木，而sum>8，所以够，sum更新为11

于是所有小朋友都能完成自己的作品，输出YES

#include<iostream> #include<vector> #include<algorithm> using namespace std; struct bricks//积木结构体，have表拥有的积木，need表需要的积木 { int have,need; }b; vector<bricks> I,E;//I，E 与上面含义相同 int cmp(bricks a,bricks b)//I组排序 { return (a.need-a.have)<(b.need-b.have); } int main() { int m,n,sum=0,flag=1;//flag为是否够得标志，sum与上面含义相同 cin>>m; for(int i=0;i<m;i++) { sum=0;//每次都置零 flag=1; I.clear(); E.clear(); cin>>n; for(int j=0;j<n;j++) { cin>>b.have>>b.need; if(b.have>b.need)//分组，如果自己的积木够完成作品，分到E组 { E.push_back(b); sum+=b.have; } else//不能完成分到I组 I.push_back(b); } sort(I.begin(),I.end(),cmp);//排序 for(vector<bricks>::iterator k=I.begin();k!=I.end();k++) { if(sum<((*k).need-(*k).have))//不够的情况 { flag=0; break; } else//够得话更新sum sum+=(*k).have; } if(flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }