http://poj.org/problem?id=3040
思路:
输入时,如果有大于c的,直接把数量加到结果中,不把他加到数组中
把钱按面值排序
想取最大面额的钱,保证取到的钱小于等于c
然后取最小面额的钱
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
int main(){
int n,c;
cin>>n>>c;
int ans=;
vector<pair<int,int> > v;
for(int i=;i<n;i++){
int a,b;
cin>>a>>b;
if(a>=c)
ans+=b;
else
v.push_back(make_pair(a,b));
}
int use[];
sort(v.begin(),v.end());
while(true){
int money=;
memset(use,,sizeof(use));
int flag=;//1表示成立 0不成立
for(int i=v.size()-;i>=;i--){
if(v[i].second!=){
int amount=(c-money)/v[i].first;
int minn=min(amount,v[i].second);
// v[i].second-=minn; 不能这样取了就直接减到.因为可能目前这种取法,并不成立
money+=v[i].first*minn;
use[i]=minn;
if(money==c){
flag=;
break;
}
}
}
if(flag==){
for(int j=;j<v.size();j++){
if(v[j].second!=&&v[j].second>use[j]){
int diff=c-money;
int amount=diff/v[j].first;
if(amount==)//如果0,说明当前的差值小于c,所以只要再取一个,就可以大于c
amount=;
int minn=min(amount,v[j].second);
money+=v[j].first*minn;
use[j]+=minn;
if(money>=c){
flag=;
break;
}
}
}
}
if(flag==){
int minn=INT_MAX;
for(int i=;i<v.size();i++){
if(use[i]!=){
minn=min(minn,v[i].second/use[i]);
}
}
ans+=minn;
for(int i=;i<v.size();i++){
if(use[i]!=){
v[i].second-=use[i]*minn;
}
}
}
else{
break;
}
}
cout<<ans<<endl;
return ;
}