1.一定注意evenly divided
也就是后一个硬币的面额一定是前一个的倍数，典型的1,3,6,9  1,2,4,8等，如果数据集满足这个性质，我的程序就会是正确的，否则就会出错
2.给一组数据，正是这组数据拯救了我
4 7
9 1
6 1
1 0
3 2
3.贴上代码仅供参考
#include <cstdio>
#include <utility>
#include <algorithm> 
#include <functional>
using namespace std;
int make(pair<int, int>* coin, int N, int C){
	int use[20], last = N-1;
	while(coin[last].second == 0)last--;
	for(int i = 0 ; i <= last ; i++){
		use[i] = coin[i].second < (C / coin[i].first) ? coin[i].second : (C / coin[i].first);
		C -= use[i] * coin[i].first;
	} 
	while(last >= 0 && C > 0){
		int cnt = 1;
		while(cnt <= (coin[last].second - use[last]) && C > coin[last].first * cnt)
			cnt++;
		if(C > coin[last].first * cnt){
			C += use[last] * coin[last].first;
			coin[last].second = 0;
			last--;
		}
		else if(cnt <= (coin[last].second - use[last])){
			C -= coin[last].first * cnt;
			use[last] += cnt;
		}
	}
	if(C > 0)
		return 0;
	int min = 1000000;
	for(int i = 0;i <= last;i++){
		if(use[i])
			min = coin[i].second / use[i] < min ? coin[i].second / use[i] : min;
	}
	for(int i = 0;i <= last;i++)
		coin[i].second -= use[i] * min;
	return min;
}
int main() {
	int N, C;
	pair<int , int> coin[20];
	int total = 0;
	scanf("%d%d", &N, &C);
	for(int i = 0;i<N;i++)
		scanf("%d%d", &coin[i].first, &coin[i].second);
	sort(coin, coin+N, greater<pair<int, int> >());
	while(int num = make(coin, N, C))
		total += num;
	printf("%d\n", total);			
	return 0;
}

• Re:这数据貌似有问题诶 (65) liu_cheng_ao 2016-10-08 16:22:02
  • 前排膜 (13) sysjuruo 2018-05-05 00:20:26