Description
在byteotian公司搬家的時候，他們發現他們的大量的精密砝碼的搬運是一件惱人的工作。公司有一些固定容 量的容器可以裝這些砝碼。他們想裝盡量多的砝碼以便搬運，并且丟棄剩下的砝碼。每個容器可以裝的砝碼數量有 限制，但是他們能夠裝的總重量不能超過每個容器的限制。一個容器也可以不裝任何東西。任何兩個砝碼都有一個 特征，他們的中總有一個的重量是另外一個的整數倍，當然他們也可能相等。 Input
第一行包含兩個數n和m。表示容器的數量以及砝碼的數量。(1<=n, m<=100000) 第二行包含n個整數wi，表示 每個容器能夠裝的最大質量。(1<=wi<=1000000000) 第三行包含m個整數mj，表示每個砝碼的質量。(1<=mj<=10000 00000) Output
僅包含一個數，為能夠裝進容器的最多的砝碼數量。 Sample Input 2 4
13 9
4 12 2 4 Sample Output 3
解題方法： 蒟蒻實在是不會做，ORZ http://hzwer.com/4761.html
#include <bits/stdc++.h>using namespace std;const int maxn = 100005;int n, m, tot, a[maxn], b[maxn], c[55], cnt[55];bool check(int x){ for(int i = x + 1; i <= tot; i++){ if(cnt[i]){ cnt[x] += c[i] / c[x]; cnt[i]--; return 1; } } return 0;}int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = 1; i <= m; i++) scanf("%d", &b[i]); sort(b + 1, b + m + 1); for(int i = 1; i <= m; i++){ if(b[i] != b[i-1]){ c[++tot] = b[i]; } } for(int i = 1; i <= n; i++){ for(int j = tot; j; j--){ while(c[j] <= a[i]){ a[i] -= c[j]; cnt[j]++; } } } int now = 1; for(int i = 1; i <= m; i++){ while(b[i] > c[now]) now++; if(cnt[now]) cnt[now]--; else if(check(now)) cnt[now]--; else{新聞熱點
疑難解答
