题目链接

Allowance POJ - 3040

思路

先确定一个当前最优的放置模式，然后看一下符合这个模式的规则。

最优的组合方式是先放大的到不溢出，如果不够再挑一个最小的补上。

时间复杂度

$$ O(N^2) $$

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 30;
const int INF = 0x3f3f3f3f;

int a[MAXN], b[MAXN], id[MAXN], num[MAXN];

bool cmp(int x, int y) {
    return a[x] > a[y];
}

int main() {
    int n, c;
    scanf("%d%d", &n, &c);// don't forget &
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i], &b[i]);// don't forget &
        id[i] = i;
        if (a[i] >= c) {
            ans += b[i];
            b[i] = 0;
        }
    }
    sort(id + 1, id + 1 + n, cmp);
    bool f = true;
    while (f) {
        int r = c;
        for (int i = 1; i <= n; i++) {
            int x = id[i];
            num[x] = min(b[x], r / a[x]);
            r -= num[x] * a[x];
        }
        for (int i = n; i >= 1; i--) {
            if (r <= 0) {
                break;
            }
            int x = id[i];
            if (b[x] > num[x]) {
                num[x]++;
                r -= a[x];
            }
        }
        if (r > 0) {
            break;
        }
        int k = INF;
        for (int i = 1; i <= n; i++) {
            int x = id[i];
            if (num[x] != 0) {
                k = min(k, b[x] / num[x]);
            }
        }
        ans += k;
        for (int i = 1; i <= n; i++) {
            int x = id[i];
            b[x] -= num[x] * k;
        }
    }
    printf("%d\n", ans);
    return 0;
}