poj3040 Allowance

思路：

贪心。

看了题解说是

先把面值从大到小排序
然后从头往尾扫，只要不超额，能取多少去多少
然后如果还有剩余，就从尾往头扫，尽量取，让他恰好超额

不过并不懂证明。

实现：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int N, C;
 7 struct node
 8 {
 9     int d, c;
10 };
11 node a[25];
12 
13 bool cmp(const node & a, const node & b)
14 {    
15     return a.d > b.d;
16 }
17 
18 int main()
19 {
20     cin >> N >> C;
21     for (int i = 0; i < N; i++)
22     {
23         scanf("%d %d", &a[i].d, &a[i].c);
24     }
25     sort(a, a + N, cmp);
26     int cnt = 0;
27     int j = 0;
28     for (; j < N; j++)
29     {
30         if (a[j].d < C)
31             break;
32     }
33     for (int i = 0; i < j; i++)
34     {
35         cnt += (a[i].d / C) * a[i].c;
36     }
37     while (true)
38     {
39         int now = 0;
40         for (int i = j; i < N; i++)
41         {
42             while (a[i].c && now + a[i].d <= C)
43             {
44                 now += a[i].d;
45                 a[i].c--;
46             }
47         }
48         for (int i = N - 1; i >= j; i--)
49         {
50             while (a[i].c && now < C)
51             {
52                 now += a[i].d;
53                 a[i].c--;
54             }
55         }
56         if (now < C)
57             break;
58         cnt++;
59     }
60     cout << cnt << endl;
61     return 0;
62 }