题目大意：给一个人发工资，给出不同数量不同面额，（大面额一定是小面额的倍数），问最多能发几天，（每天实发工资>=应发工资）。
思路：首先，将大于等于c的面额的钱直接每个星期给奶牛一张，将面额大于等于c的前去除。然后从大到小开始选择，要选择的金额尽可能的接近c，如果刚好能够凑足c就作为当前的一种方案，如果不能凑足c那就再从小的开始选，要选出一种的总额不少于c但尽量接近c作为当前的方案，然后计算如果按照如此方案最多可以给奶牛多少周，然后按照相同的方法再选方案，一直选到选择的金额不能凑足c为止。
为什么这样做是对的呢？
题目中说大面值一定是小面值的倍数，所以，如果一个数字可以用大面值凑，那必定可以用小面值凑，也就是说，小面值的功能比大面值强。我们在能选择大面值的时候，尽量选择大面值。在这个过程中我们一直保证m<=c,但如果我们不能使m<=c，即即便我们用了最小的面额也会超值，那就只能浪费超过的这一部分了，并且此时浪费的是最少的。（如果先选小的再选大的，浪费的肯定大于等于此时的情况）
代码。
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<bitset>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define CLR(x,y) memset(x,y,sizeof(x))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
using namespace std;
typedef long long ll;
struct dian {
int val,to;
} a[30];
bool cmp(dian a,dian b) {
return a.val<b.val;
}
int make[30];
int main() {
int n,c;
cin>>n>>c;
for(int i=1; i<=n; i++) {
cin>>a[i].val>>a[i].to;
}
sort(a+1,a+1+n,cmp);
int ans=0;
for(int i=n; i>0; i--) {
if(a[i].val>=c) {
ans+=a[i].to;
n--;
} else break;
}
bool flag;
while(1) {
flag=false;
memset(make,0,sizeof(make));//make表示 某一种货币在一种工资组合中的使用次数
int tepc=c;
int i;
for(i=n; i>0; i--) {
if(a[i].to) {
int m,num;
num=tepc/a[i].val;
m=min(num,a[i].to);//尽可能的多用，但不能超过总数
tepc-=m*a[i].val;
make[i]=m;
if(tepc==0) { //此处只会>=0
flag=true;
break;
}
}
}
if(tepc>0) {
for(i=1; i<=n; i++) {
if(a[i].to>make[i]) {//make里面存的是当前这一轮用过的 除了用过的 还有剩下的 才可以用这种货币
while(make[i]<a[i].to) {
tepc-=a[i].val;
make[i]++;
if(tepc<0) {//此处不会=0 因为=0的情况上面已经排除掉了
flag=true;
break;
}
}
}
if(flag)break;
}
}
if (!flag) break;
int cnt=0x3f3f3f3f;
for(int i=1;i<=n;i++){
if(make[i])
cnt=min(cnt,a[i].to/make[i]);//最小的组合
}
ans+=cnt;
for(int i=1;i<=n;i++){
a[i].to-=make[i]*cnt;
}
}
cout<<ans<<endl;
}Allowance
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 5167 | Accepted: 2032 |
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 ompute the maximum number of weeks he can pay Bessie.
Input
* Line 1: Two space-separated integers: N and C
* Lines 2..N+1: Each line corresponds to a denomination of coin and contains two integers: the value V (1 <= V <= 100,000,000) of the denomination, and the number of coins B (1 <= B <= 1,000,000) of this denomation in Farmer John's possession.
* Lines 2..N+1: Each line corresponds to a denomination of coin and contains two integers: the value V (1 <= V <= 100,000,000) of the denomination, and the number of coins B (1 <= B <= 1,000,000) of this denomation in Farmer John's possession.
Output
* Line 1: A single integer that is the number of weeks Farmer John can pay Bessie at least C allowance
Sample Input
3 6 10 1 1 100 5 120
Sample Output
111
Hint
INPUT DETAILS:
FJ would like to pay Bessie 6 cents per week. He has 100 1-cent coins,120 5-cent coins, and 1 10-cent coin.
OUTPUT DETAILS:
FJ can overpay Bessie with the one 10-cent coin for 1 week, then pay Bessie two 5-cent coins for 10 weeks and then pay Bessie one 1-cent coin and one 5-cent coin for 100 weeks.
FJ would like to pay Bessie 6 cents per week. He has 100 1-cent coins,120 5-cent coins, and 1 10-cent coin.
OUTPUT DETAILS:
FJ can overpay Bessie with the one 10-cent coin for 1 week, then pay Bessie two 5-cent coins for 10 weeks and then pay Bessie one 1-cent coin and one 5-cent coin for 100 weeks.