P2376 [USACO09OCT]津贴Allowance

这道题其实就是个贪心，先选大的，后考虑小的，在实现时注意细节就好了
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #define II int
 5 #define B bool
 6 #define R register
 7 #define I 123456
 8 using namespace std;
 9 
10 struct node {
11     II buy,nu;
12 }aa[I];
13 
14 II n,c,ans;
15 
16 B maP(node a1,node a2) { return a1.buy>a2.buy; }
17 
18 int main()
19 {
20     freopen("1.in","r",stdin);
21 
22     scanf("%d%d",&n,&c);
23     for(R II i=1;i<=n;i++)
24     {
25         scanf("%d%d",&aa[i].buy,&aa[i].nu);
26     } 
27 
28     sort(aa+1,aa+n+1,maP);
29 
30     R II now=1, en=n;
31     while (aa[now].buy>=c) {
32         ans+=aa[now].nu;
33         now++;
34     }
35 
36     while (1) {
37         R II ka=c;
38         // 小技巧; 
39         for(R II i=now;i<=n;i++)
40         // 所谓的从大到小贪心就是这个枚举顺序了; 
41         {
42             while (ka>=aa[i].buy&&aa[i].nu&&ka>0) {
43                 ka-=aa[i].buy;
44                 aa[i].nu--;
45             }
46             // 一直减到不能再减为止，然后换下一个值;
47         } 
48         if(ka>0) for(R II i=n;i>=now;i--) {
49             if(aa[i].buy>=ka&&aa[i].nu) {
50                 aa[i].nu--;
51                 ka-=aa[i].buy;
52                 break ;
53             }
54         }
55         // 找一个大于剩余值且最小的, 补全; 
56         if(ka>0) break ;
57         // 如果还不行，证明剩下的组不成c了，结束; 
58         ans++;
59     }
60 
61     printf("%d
",ans);
62     exit(0);
63 }