Descriptions:

作为创纪录的牛奶生产的奖励，农场主约翰决定开始给Bessie奶牛一个小的每周津贴。FJ有一套硬币N种（1≤N≤20）不同的面额，每枚硬币是所有比他小的硬币面值的倍数，例如1美分硬币、5美分硬币、10美分硬币和50美分硬币。使用这些硬币，FJ每周至少给Bessie C（1 <= C <=100000000）美分。请你计算他最多能给Bessie几周

Input

第一行N 、 C
第 2..N+1行: 硬币价值 V (1 <= V <= 100,000,000) 和数量 B (1 <= B <= 1,000,000)

Output

使用这些硬币，每周至少给C美分的前提下的最多周数

Sample Input

    3 6
    10 1
    1 100
    5 120

Sample Output

    111

输出提示

FJ给Bessie 10美分一周；给Bessie 5美分和1美分一百周；给Bessie 两枚5美分十周

题解

贪心策略是使多发的面额最小（最优解）。

分三个阶段：

• 1.首先面额不小于C的硬币属于没办法节约的类型，先统统发掉。

• 2.然后对硬币面额从大到小尽量凑得接近C，允许等于或不足C，但是不能超出C。

• 3.接着按硬币面额从小到大凑满C（凑满的意思是允许超出一个最小面值，最小面值指的是硬币剩余量不为0的那些硬币中的最小面值），凑满之后得出了最优解，发掉，进入步骤2.

这样就保证了每次都是当前的最优解

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
using namespace std;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
typedef pair<int,int> PII;
typedef long long LL;

const int N=25;
PII coin[N];
int n,m;

int main()
{
    cin>>n>>m;

    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        cin>>coin[i].first>>coin[i].second;
        if(coin[i].first >= m)
        {
            cnt+=coin[i].second;
            coin[i].second=0;
        }
    }

    sort(coin+1,coin+n+1,greater<PII>());

    while(1)
    {
        int now=0;
        for(int i=1;i<=n;i++)
            if(coin[i].second)
            {
                while(coin[i].second && now + coin[i].first <= m)
                    now+=coin[i].first,coin[i].second--;
            }

        for(int i=n;i>=1;i--)
            if(coin[i].second)
            {
                while(coin[i].second && now < m)
                    now+=coin[i].first,coin[i].second--;
            }

        if(now < m) break;
        cnt++;
    }

    cout<<cnt<<endl;

   // system("pause");
}