【题解】EOJ-102-发工资

Posted on In Disqus:

题目

https://acm.ecnu.edu.cn/problem/102/

题意

自行读题。

题解

  • 乱搞（贪心）题。
  • 题目中保证了面额小的都能整除大的。所以对于某一种方案，若干张面额小的用一张面额大的替换一定是更优的。因为如果将来需要用到这个面额大的，可以用省下来的若干张面额小的来替代，而且增加了灵活性。
  • 如果凑不出刚好的，那么肯定要浪费一些钱，此时浪费的钱肯定越少越好。首先尽可能得接近目标值，达不到的部分可以用一张面额尽可能小的钞票解决（为什么是一张？跨过目标值的肯定是恰好一张。）
  • 具体实现：排序，在不超出目标值的前提下贪心选择大的。如果没凑出整的，那么再从小到大考虑并选取一张。对于这个方案，执行尽可能多的次数（否则会超时）。
  • 复杂度：寻找一个方案是 \(O(n)\)，每一趟的方案一定不同，所以复杂度肯定不超过 \(O(n 2^n)\)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int maxn = 20 + 100;
LL v[maxn], k[maxn];
LL n, c, ans;

struct P {
    LL v, k;
};
vector<P> p;

bool go(vector<P>& p) {
    sort(p.begin(), p.end(), [](const P& a, const P& b){ return a.v < b.v; });
    static LL t[maxn]; memset(t, 0, sizeof t);
    LL cc = c, cnt = 1E18;
    for (int i = (int)p.size() - 1; i >= 0; --i) {
        t[i] = min(p[i].k, cc / p[i].v);
        cc -= t[i] * p[i].v;
    }
    for (int i = 0; i < (int)p.size(); ++i)
        if (cc > 0 && p[i].k - t[i] > 0) {
            cc -= p[i].v;
            ++t[i];
            break;
        }
    if (cc > 0) return false;

    for (int i = 0; i < (int)p.size(); ++i) {
        if (t[i]) cnt = min(cnt, p[i].k / t[i]);
    }
    for (int i = 0; i < (int)p.size(); ++i)
        p[i].k -= cnt * t[i];

    ans += cnt;
    return true;
}

int main() {
    cin >> n >> c;
    for (int i = 0; i < n; ++i) cin >> v[i] >> k[i];
    for (int i = 0; i < n; ++i) p.push_back({v[i], k[i]});
    while (go(p));
    cout << ans << endl;
}