首页 > 代码库 > POJ 3040 贪心
POJ 3040 贪心
链接:
http://poj.org/problem?id=3040
题解:
1:大于c的就直接取;
2:如果小于就从大到小拿钱,能拿多少拿多少,但不能超过c;
3:如果2拿的钱小于c,就从小到大拿钱,能拿多少拿多少,但要求是超过c的时候是最小的,也就是说,这些钱的总和是大于c的最小数;
4:将此类取钱方式求出次数,加到ans中,然后返回第二步。
代码:
1 #include <map> 2 #include <set> 3 #include <cmath> 4 #include <queue> 5 #include <stack> 6 #include <cstdio> 7 #include <string> 8 #include <vector> 9 #include <cstdlib> 10 #include <cstring> 11 #include <sstream> 12 #include <iostream> 13 #include <algorithm> 14 #include <functional> 15 using namespace std; 16 #define rep(i,a,n) for (int i=a;i<n;i++) 17 #define per(i,a,n) for (int i=n-1;i>=a;i--) 18 #define all(x) (x).begin(),(x).end() 19 #define pb push_back 20 #define mp make_pair 21 #define lson l,m,rt<<1 22 #define rson m+1,r,rt<<1|1 23 typedef long long ll; 24 typedef vector<int> VI; 25 typedef pair<int, int> PII; 26 const ll MOD = 1e9 + 7; 27 const int INF = 0x3f3f3f3f; 28 const int MAXN = 5e4 + 7; 29 // head 30 31 struct Coin { 32 int v, b; 33 const bool operator<(const Coin &c) const { 34 return v < c.v; 35 } 36 }a[30]; 37 38 int use[30]; 39 40 int main() { 41 int n, c; 42 cin >> n >> c; 43 rep(i, 0, n) scanf("%d%d", &a[i].v, &a[i].b); 44 int ans = 0; 45 rep(i, 0, n) if (a[i].v >= c) { 46 ans += a[i].b; 47 a[i].b = 0; 48 } 49 sort(a, a + n); 50 while (1) { 51 int sum = c; 52 memset(use, 0, sizeof(use)); 53 per(i, 0, n) if (a[i].b && sum) { 54 use[i] = min(a[i].b, sum / a[i].v); 55 sum -= use[i] * a[i].v; 56 } 57 rep(i, 0, n) if (a[i].b && sum) { 58 int t = min(a[i].b - use[i], (sum + a[i].v - 1) / a[i].v); 59 sum -= t*a[i].v; 60 use[i] += t; 61 } 62 if (sum > 0) break; 63 int x = INF; 64 rep(i, 0, n) if (use[i]) x = min(x, a[i].b / use[i]); 65 ans += x; 66 rep(i, 0, n) if (use[i]) a[i].b -= x*use[i]; 67 } 68 cout << ans << endl; 69 return 0; 70 }
POJ 3040 贪心
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。