小记:这题想的真头疼,还好想出来了头绪,证明的解法确实是正确的
思路:将Bi和Ai的差值进行从大到小的排序,这样依次贪心,然后计算是否可以全部存放进去。
可以证明如果这样的排好的一个次序不能全部存放进去的话,那么结果就是不行的,反之即代表是可行的
代码:
#include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #include <map> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> using namespace std; #define mst(a,b) memset(a,b,sizeof(a)) #define REP(a,b,c) for(int a = b; a < c; ++a) #define eps 10e-8 const int MAX_ = 5010; const int N = 100010; const int INF = 0x7fffffff; struct node{ int s, e; }t[MAX_]; int vis[MAX_]; bool cmp(const node& a, const node& b) { return (a.e-a.s) > (b.e-b.s); } int main() { int T; int n, m; scanf("%d",&T); while(T-- && scanf("%d%d",&n, &m)) { int ans = 0; int cnt = 0, ss, tt; REP(i, 0, m) { scanf("%d%d", &t[i].s, &t[i].e); } sort(t,t+m,cmp); bool flag = 0; REP(i, 0, m){ if(n >= t[i].e){ n -= t[i].s; } else { flag = 1; break; } } if(!flag)printf("Yes\n"); else printf("No\n"); } return 0; }