There are several cases.
For each case, First line there is a n, indicate n stations. Then n lines followed, each line has two numbers xi and yi. To make the problem easier, we guarantee that xi>=yi.(0<n<100000 0<=xi,yi<1000000)2 5 0 7 4 2 5 2 3 3
Yes No
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<stdlib.h> #include<vector> #include<queue> #include<stack> #include<algorithm> #define LL long long using namespace std; const int MAXN=100000+5; LL tot; int n; struct node { int x,y; bool operator<(const node A)const { return x-y>A.x-A.y; } }a[MAXN]; bool cheak() { for(int i=0;i<n;i++) { if(tot<a[i].x) return false; tot-=a[i].y; } return true; } int main() { while(scanf("%d",&n)!=EOF) { tot=0; for(int i=0;i<n;i++) { scanf("%d %d",&a[i].x,&a[i].y); tot+=(a[i].x-a[i].y); a[i].y=(a[i].x-a[i].y); } sort(a,a+n); puts(cheak()?"Yes":"No"); } return 0; }
ACDream 1734 Can you make a water problem?(贪心)
原文：http://www.cnblogs.com/clliff/p/4491467.html
