【题解】EOJ-102-发工资

题目

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;
}