题解：P4765 [CERC2014] The Imp

· · 题解

模拟赛 T3，但是 n\le 10^5,k\le 20 只有 80 分。A_zjzj 是这样的。

很容易想到这个题复杂度是 O(nk) 的。

首先有个结论：对于所有要选的货物，v_i 不严格单调递增。

考虑两个货物，价格分别是 v_1,v_2，v_1<v_2，升序的代价是 \min(v_1-c_1,v_2-c_1-c_2)，降序的代价是 \min(v_1-c_1-c_2,v_2-c_2)。

很显然 v_1-c_1 和 v_2-c_1-c_2 都比 v_1-c_1-c_2 大，所以升序更优。

我们考虑设计 dp，令 dp_{i,j} 表示前 i 个货物被毁了 j 个的最大利润，很显然先手可以选或不选，如果选了小恶魔可以选择毁掉或不毁掉，所以容易写出转移式。

dp_{i,j}=\max(dp_{i-1,j},\min(dp_{i-1,j-1}-c_i,v_i-c_i))

注意 dp_{i,0}=v_i-c_i，复杂度 \mathcal{O}(nk)。

#include<bits/stdc++.h>
using namespace std;
#define I inline
#define int long long
namespace SlowIO {
    const int SZ = (1 << 20) + 1;
    char buf[SZ], *p1 = buf, *p2 = buf;
    char buffer[SZ];
    int op1 = -1;
    const int op2 = SZ - 1;
    I char gc() {
        if(p1 != p2) return *p1++;
        return p1 == (p2 = (p1 = buf) + fread(buf, 1, SZ - 1, stdin)) ? EOF : *p1++;
    }
    I void flush() {
        fwrite(buffer, 1, op1 + 1, stdout);
        op1 = -1;
    }
    I void pc(const char &x) {
        if(op1 == op2) flush();
        buffer[++op1] = x;
    }
    I int read() {
        int x = 0, f = 1; char ch = gc();
        while(ch < '0' || ch > '9') {if(ch == '-') f = -f; ch = gc();}
        while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gc();
        return x * f;
    }
    I void write(int x) {
        if(x < 0) pc('-'), x = -x;
        if(!x) {pc('0'); return ;}
        char s[25];
        int tot = 0;
        while(x || !tot) {
            s[tot++] = x % 10 + 48;
            x/=10;
        }
        while(tot--) pc(s[tot]);
    }
} using namespace SlowIO;
const int N = 150010;
int n, m;
int dp[N][22];
struct node {
    int A, B;
} a[N], b[N];
bool cmp(node a, node b) {
    return a.B > b.B;
}
signed main() {
    int T = read();
    while(T--) {
        n = read(), m = read();
        for(int i = 1; i <= n; i++) a[i].B = read(), a[i].A = read();
        sort(a + 1, a + 1 + n, cmp);
        for(int i = 1; i <= n; i++) {
            dp[i][0] = max(dp[i - 1][0], a[i].B - a[i].A);
            for(int j = 1; j <= m; j++) {
                dp[i][j] = max(dp[i - 1][j], min(dp[i - 1][j - 1] - a[i].A, a[i].B - a[i].A));
            }
        }
        write(dp[n][m]); pc('\n');
    }
    flush();
    return 0;
}

但是模拟赛题的数据被 A_zjzj 加强成了 k\le n，所以这个代码只有 80 分。（当然你判个 v_i=c_i 的情况，能有 85 分）

正解是反悔贪心。

继续沿用前面的结论：对于所有要选的货物，v_i 不严格单调递增。

考虑二分答案。

只要我们能够选出选出 m+1 个物品，满足每个物品的售价减去前面所有物品的代价大于等于答案就行了。

然后如果物品可行就直接加，否则考虑反悔，和前面加入的最贵的弹出去。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 150010;
int n, m;
struct node {
    int A, B;
} a[N];
bool cmp(node a, node b) {
    return a.B < b.B;
}
bool chk(int mid) {
    priority_queue<int> q;
    while(!q.empty()) q.pop();
    int sum = 0, cnt = 0;
    for(int i = 1; i <= n; i++) {
        if(a[i].B - a[i].A - sum >= mid) {
            cnt++;
            sum += a[i].A;
            q.push(a[i].A);
        }
        else {
            if(!q.empty() && q.top() > a[i].A) {
                sum -= q.top();
                sum += a[i].A;
                q.pop(); q.push(a[i].A);
            }
        }
        if(cnt == m + 1) return 1;
    }
    return 0;
}
signed main() {
    ios::sync_with_stdio(0);
    int T; cin >> T;
    while(T--) {
        cin >> n >> m;
        for(int i = 1; i <= n; i++) cin >> a[i].B >> a[i].A;
        sort(a + 1, a + 1 + n, cmp);
        int l = 1, r = 1e18, ans = 0;
        while(l <= r) {
            int mid = l + r >> 1;
            if(chk(mid)) ans = mid, l = mid + 1;
            else r = mid - 1;
        }
        cout << ans << '\n';
    }
    return 0;
}