思路: 感觉脑洞好大啊... 因为每两个砝码其中一个都是另一个的倍数, 我们可以知道砝码的种数很少, 我们将所有容器的
容量都转换成用这些砝码的重量的进制表示, 然后将所有砝码排序, 然后贪心地取, 取到不能再取.
- #include<bits/stdc++.h>
- #define LL long long
- #define fi first
- #define se second
- #define mk make_pair
- #define pii pair<int, int>
- using namespace std;
- const int N = 1e5 + 7;
- const int inf = 0x3f3f3f3f;
- const LL INF = 0x3f3f3f3f3f3f3f3f;
- const int mod = 1e9 +7;
- int n, m, w[N], a[N], b[N], cnt[50], tot;
- int main() {
- scanf("%d%d", &n, &m);
- for(int i = 1; i <= n; i++) {
- scanf("%d", &w[i]);
- }
- for(int i = 1; i <= m; i++) {
- scanf("%d", &a[i]);
- b[tot++] = a[i];
- }
- sort(b, b + tot);
- tot = unique(b, b + tot) - b;
- reverse(b, b + tot);
- for(int i = 1; i <= n; i++) {
- int now = w[i];
- for(int j = 0; j <tot && now; j++) {
- cnt[j] += now / b[j];
- now = now % b[j];
- }
- }
- int ans = 0;
- sort(a + 1, a + 1 + m);
- for(int i = 1; i <= m; i++) {
- for(int j = tot - 1; j>= 0; j--) {
- if(b[j] == a[i]) {
- if(cnt[j]) {
- cnt[j]--;
- ans++;
- break;
- } else {
- int pos = -1;
- for(int k = j - 1; k>= 0; k--) {
- if(cnt[k]) {
- pos = k;
- break;
- }
- }
- if(pos == -1) {
- i = m + 1;
- break;
- }
- for(int k = pos + 1; k <= j; k++) {
- cnt[k - 1]--;
- cnt[k] += b[k - 1] / b[k];
- }
- ans++;
- cnt[j]--;
- break;
- }
- }
- }
- }
- printf("%d\n", ans);
- return 0;
- }
- /*
- */
来源: http://www.bubuko.com/infodetail-2648403.html