POJ-3040 : Allowance

問題概要

n(<20)種類のコインがある。コインの価値は倍数列になっている。各種類毎に何枚あるかが与えられる(num[i]<10^8)。C(<10^8)円以上の組がいくつ作れるか求める問題。

解法

コインの価値が高い順にCを越えないよう貪欲に詰めていく。次に、価値が低い順にCをぎりぎり越えるように貪欲に詰めていけばよい。うまく行く理由としては、まず前半の価値が高い順に越えないよう貪欲に詰めるのは倍数列の制約から明らかとなる。後半に低い順に価値をぎりぎり越えるように詰めていくのをより高いコインで置き換えても後により価値の低いコインしか残らず、それを高いコインで置き換えた方がよいからである。日本語めちゃくちゃだけどそんなに直感から外れた戦略ではない。

acceptされたコード

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

const int INF = (int)(2.05e9); 

template<typename numType>
inline bool updateMin(numType& old, const numType& test) {
	if (old > test) {
		old = test;
		return true;
	}
	return false;
}

const int MAX_N = 20;
int N, C;
pair<int,int> items[MAX_N]; 
int curUse[MAX_N];

void init() {
	scanf("%d%d", &N, &C);
	for (int i = 0; i < N; ++i) {
		int val, num;
		scanf("%d%d", &val, &num);
		items[i] = make_pair(val, num);
	}
}

int solve() {
	sort(items, items + N);
	int ans = 0;
	for (int i = 0; i < N; ++i) if (items[i].first >= C) {
		ans += items[i].second;
		items[i].second = 0;
	}

	reverse(items, items + N);

	for (;;) {
		int curVal = 0;
		memset(curUse, 0, sizeof(curUse));
		for (int i = 0; i < N; ++i) if (items[i].second > 0 && curVal < C) {
			int use = min(items[i].second, (C - curVal) / items[i].first);
			if (use > 0) {
				curUse[i] = use;
				curVal += use * items[i].first;
			}
		}

		for (int i = N - 1 ; i >= 0; --i) if (items[i].second > 0 && curVal < C) {
			int use = min(items[i].second - curUse[i], (C - curVal + items[i].first - 1) / items[i].first);
			if (use > 0) {
				curUse[i] += use;
				curVal += use * items[i].first;
			}
		}


		if (curVal < C) {
			break;
		}
		int add = INF;
		for (int i = 0; i < N; ++i) if (curUse[i] > 0) {
			updateMin(add, items[i].second / curUse[i]);
		}
		ans += add;
		for (int i = 0; i < N; ++i) if (curUse[i] > 0) {
			items[i].second -= add * curUse[i];
		}
	}

	return ans;
}

int main() {
	init();
	printf("%d\n", solve());
	return 0;
}