POJ 3040 Allowance （貪心）

Allowance

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 1696	Accepted: 708

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.

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      

= = 貪心思路比較明顯 但是不是很好寫 先從大到小嘗試拼湊一次工資量 然後不夠的用一個小的補齊

最後确定發工資量 然後更新剩餘的硬币 在嘗試後仍不能拼湊一次工資量 就退出循環

- - 貪心模拟感覺不好很好寫 還是代碼能力不夠 想的不夠多

AC代碼如下：

//
//  POJ 3040 Allowance
//
//  Created by TaoSama on 2015-02-22
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
#define CLR(x,y) memset(x, y, sizeof(x))

using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;

struct Coin {
	int v, c;
	bool operator<(const Coin& rhs) const {
		return v > rhs.v;
	}
} a[25];
int n, p, need[25];

int main() {
#ifdef LOCAL
	freopen("in.txt", "r", stdin);
//	freopen("out.txt","w",stdout);
#endif
	ios_base::sync_with_stdio(0);

	while(cin >> n >> p) {
		for(int i = 1; i <= n; ++i)
			cin >> a[i].v >> a[i].c;
		sort(a + 1, a + 1 + n);
		int ans = 0;
		while(true) {
			int rest = p; 		//發一次工資
			memset(need, 0, sizeof need);
			for(int i = 1; i <= n; ++i) {   //從大到小嘗試
				if(a[i].c > 0) {
					int t = min(a[i].c, rest / a[i].v);
					rest -= t * a[i].v;
					need[i] = t;
				}
				if(rest == 0) break;
			}
			if(rest > 0) {
				for(int i = n; i > 0; --i) { //用小的補齊 抑或最後大于p的
					if(a[i].c > 0 && a[i].v >= rest) {
						rest = 0;
						++need[i];
						break;
					}
				}
			}
			if(rest > 0) break;  //還剩下的說明不能了
			int add = INF;
			for(int i = 1; i <= n; ++i) //擷取發工資次數
				if(need[i])
					add = min(add, a[i].c / need[i]);
			for(int i = 1; i <= n; ++i) //更新剩餘硬币
				if(need[i])
					a[i].c -= add * need[i];
			ans += add;
		}
		cout << ans << endl;
	}
	return 0;
}