题意:每个数据的第一行是两个正整数n和s,1≤n≤10000,1≤s≤1000000,表示一共有n位小朋友,The Pancakes手上有s块积木。以下有n行,每行有两个正整数,a和b,1≤a,b≤10^9,表示第i个小朋友手上有a块积木,还需要b块积木才能够砌完。The Pancakes能将她手上的积木给孩子满足孩子的需要,待孩子拼好后可收回包括该孩子原来积木在内的所有积木(不考虑孩子间的相互给予),问是否所有的孩子都能拼好积木,能的话输出"YES",不能的话输出"NO"。
题目链接:http://soj.me/1134
——>>简单题中的纠结,看题后可知是简单贪心即可(将孩子按各自的需要从小到大排序),却试了2次WA,因为被最后一组测试数据欺骗了:0 0,粗人的我没留意题目中的“输入n=0时表示结束”,因判断n与s同时为0才退出致使2次WA......
#include <cstdio>
#include <algorithm>using namespace std;const int maxn = 10000 + 10;
struct node
{int a;int b;bool operator < (const node& e) const{return b < e.b || (b == e.b && a > e.a);}
}x[maxn];int main()
{int n, s;while(~scanf("%d", &n)){if(!n) return 0;scanf("%d", &s);for(int i = 0; i < n; i++) scanf("%d%d", &x[i].a, &x[i].b);sort(x, x+n);bool ok = 1;for(int i = 0; i < n; i++)if(s < x[i].b){ok = 0;break;}else s += x[i].a;if(ok) printf("YES\n");else printf("NO\n");}return 0;
}