题意:一共有(N (1 <= N <= 20))种不同面额的硬币.每一个面额都能整除所有比它大的面额.每个星期至少给Bessie零花钱(M(1 <= M <= 100000000)).计算Bessie最多能有多少个星期的零花钱.
分析:贪心:先尽量用大的面额凑出(M)元.每次尽量正好凑出(M)元.
其实有了这个贪心策略,剩下的就是模拟了.首先面额大于(M)的硬币,可以直接在输入时就统计入答案,后面不予考虑.然后每次考虑如何凑出(M),并记录我们是如何凑出(M)的,方便最后统计答案时一次性计算这种方式最多能够凑出几个(M).
我们把剩下的比(M)小的硬币按照金额从小到大排序.首先倒序枚举,在不超过(M)的情况下尽量用大的面额去凑,实在凑不出正好的M元,再顺序枚举,用第一个能使凑出大于M元 一个硬币 去凑这一份.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=25;
int n,m,tot,ans,num[N];
struct ppx{int v,b;}a[N];
inline bool cmp(const ppx &x,const ppx &y){return x.v<y.v;}
int main(){
n=read();m=read();
for(int i=1;i<=n;++i){
int v=read(),b=read();
if(v>=m){ans+=b;continue;}//筛掉大于m元的硬币
a[++tot].v=v;a[tot].b=b;
}
sort(a+1,a+tot+1,cmp);//按照面额从小到大排序
while(1){
memset(num,0,sizeof(num));//记录此次如何拼出m元的
int now=m;//表示此次拼出m元,还至少要凑now元
for(int i=tot;i>=1;--i){//先倒序枚举
if(a[i].b<=0||a[i].v>now)continue;//该种面额用完了或者用了该种面额会超出m元,就不考虑
if(a[i].b>=now/a[i].v){//能用多少就用多少
num[i]+=now/a[i].v;//记录用了now/a[i].v个第i中硬币
now%=a[i].v;//更新now
}
else{//能用多少就用多少
num[i]+=a[i].b;
now-=a[i].b*a[i].v;
}
}
//这里强调一下,上面倒序循环我们试图正好凑出m元
//而下面顺序循环是我们无法正好凑出m元,说明不得不浪费一点钱
//在这种情况下,我们选择一个只要用一个硬币就能超出now元的面额
for(int i=1;i<=tot;++i){//再顺序枚举
if(now<=0)break;//已经凑好了m元
if(a[i].b<=0||now>a[i].v)continue;//该种面额用完了或者用了该种面额不会超出m元,就不考虑
now-=a[i].v;++num[i];
}
if(now>0)break;//此次不能拼出m元,以后也不能够凑出来了
int cnt=1e9;
for(int i=1;i<=tot;++i)
if(num[i])cnt=min(cnt,a[i].b/num[i]);
//按照此次凑出m的方式,我们能用cnt次这种方式
ans+=cnt;
for(int i=1;i<=tot;++i)a[i].b-=cnt*num[i];//更新剩余硬币数量
}
printf("%d
",ans);
return 0;
}