描述 Description
As a reward for record milk production, Farmer John has decided to start paying Bessie the cow a small weekly allowance. FJ has a set of coins in N (1 <= N <= 20) different denominations, where each denomination of coin evenly divides the next-larger denomination (e.g., 1 cent coins, 5 cent coins, 10 cent coins, and 50 cent coins). Using the given set of coins, he would like to pay Bessie at least some given amount of money C (1 <= C <= 100,000,000) every week. Please help him compute the maximum number of weeks he can pay Bessie.
作为对勤勤恳恳工作的贝茜的奖励，约翰已经决定开始支付贝茜一个小的每周津贴． 约翰有 n(1≤N≤20) 种币值的硬币，面值小的硬币总能整除面值较大的硬币．比如说，币值有如下几种：1 美分，5 美分，10 美分，50 美分…．．
利用给定的这些硬币，他将要每周付给贝茜一定金额的津贴 C(1≤C≤10^8)．
请帮他计算出他最多能给贝茜发几周的津贴．
输入格式 InputFormat
第 1 行：2 个用空格隔开的整数 n 和 C.
第 2 到 n+1 行：每行两个整数表示一种币值的硬币．第一个整数 V(I≤y≤10^8)，表示币值．
第二个整数 B(1≤B≤10^6)，表示约翰拥有的这种硬币的个数．
输出格式 OutputFormat
一个整数，表示约翰付给贝茜津贴得最多的周数．
样例输入 SampleInput
20 100000000
67108864 1000000
33554432 1000000
16777216 1000000
8388608 1000000
4194304 1000000
2097152 1000000
1048576 1000000
524288 1000000
262144 1000000
131072 1000000
65536 1000000
32768 1000000
16384 1000000
8192 1000000
4096 1000000
2048 1000000
1024 1000000
512 1000000
256 1000000
128 1000000
样例输出 SampleOutput
1340054
来源 Source
Silver
代码 Code
水。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int inf=0x7fffffff/11.27;
int i,j,t,n,m,l,r,k,z,y,x;
inline void read(int &x)
{
x=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
struct coin
{
int v,b;
bool operator < (const coin &temp)const
{
return v<temp.v;
}
}a[25];
int main()
{
read(n);read(m);
int ans=0;
for (i=1;i<=n;i++) read(a[i].v),read(a[i].b);
sort(a+1,a+n+1);
do
{
t=m;
for (i=n;i>0;i--)
{
k=min(a[i].b,(int)t/a[i].v);
a[i].b-=k;
t-=a[i].v*k;
}
for (i=1;i<=n;i++) if (a[i].b>0 && t>0)
{
a[i].b--;
t-=a[i].v;
}
if (t<=0) ans++;
}while (t<=0);
printf("%d\n",ans);
return 0;
}