BZOJ 1110:POI2007 砝码Odw

//真是让人难过呢。。。

Solution:

注意到任何两个砝码一个是另一个的整数被 所以可以把容量按照砝码重进行拆分 选择时贪心满足即可 如果一个小的无法满足 则可以把比它大的一个拆成多个当前大小的进行选择(给大的正好满足一个 拆成小的最少可以满足当前的一个)

Code:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100001;
int ans, bin[N], sum[N];
int n, m, ce, v[N], w[N]; // v -> 容器 w -> 砝码    
inline bool judge(int tmp) {
    if(tmp > ce) return 0; if(sum[tmp] > 0) {-- sum[tmp]; return 1;}
    else if(judge(tmp + 1)) {sum[tmp] = w[tmp + 1] / w[tmp] - 1; return 1;}
    return 0;
}
inline int read() {
    int x = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') w = 1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return w ? - x : x;
}
int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; ++ i) v[i] = read();
    for(int j = 1; j <= m; ++ j) w[j] = read();
    sort(w + 1, w + 1 + m);
    for(int i = 1; i <= m; ++ i) {
        if(w[i] == w[i - 1]) ++ bin[ce];
        else w[++ ce] = w[i], bin[ce] = 1;
    }
    for(int i = 1; i <= n; ++ i) 
    for(int j = ce; j > 0; -- j) 
        sum[j] += v[i] / w[j], v[i] %= w[j];
    for(int i = 1; i <= ce; ++ i) {
        bool flag = 1;
        while(bin[i]) {
            if(judge(i)) ++ ans, -- bin[i];
            else {flag = 0; break;}
        } if(! flag) break;
    } printf("%d", ans);
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注