# [BZOJ1685]&&[Usaco2005 Oct]Allowance 津贴

## 描述 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.

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

1340054

Silver

BZOJ 1685

## 代码 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()
{
int ans=0;
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;
}``````