这题我用的是逆向思维,从洞里把它拿出来,不用考虑先拿什么。。只要满足条件就拿出来。暴力搜索,最后竟然0ms。
看了下网上的代码用的是差值排序。。。用时还要15ms
#include#include #include using namespace std; int V[1010], L[1010]; struct node { int v, l; }T[1010]; int main( ) { int P, i, M, N, flag, v, m, flag1; scanf("%d",&P); while (P--) { flag = 0; v = 0; scanf("%d%d",&M, &N); for(i = 0; i < N; i++) { scanf("%d%d",&T[i].v,&T[i].l); v = v + T[i].v; } v = M - v; m = v; while(1) { flag1 = 0; for(i = 0;i < N ; i++) { if ( T[i].v != 0 ) { m += T[i].v; if (m >= T[i].l) flag++,T[i].l = 0, T[i].v = 0, flag1 = 1; else m -= T[i].v; } } if (!flag1) { if(flag == N) puts("Yes"); else puts("No"); break; } } } return 0; }