题解：CF1969D Shop Game

flower1 · 2025-09-01 14:20:35 · 题解

Description

有 n 个商品，Alice 以 a_i 的价格选择若干个物品进货，然后卖给 Bob。Bob 可以选择其中的 k 个免费拿走，剩下的付款 b_i 元。

Alice 希望自己的利润最大化，而 Bob 希望 Alice 的利润最小化，求 Alice 能获得的最大利润。

Solution

首先忽略所有 a_i >b_i 的物品，选择这些物品无论如何都是亏钱的。

考虑 Bob 会如何行动，为了使 Alice 收益最小，Bob 一定会免费拿走 b_i 前 k 大的物品。

考虑 Alice 会如何行动，设 Bob 拿走的物品 b_i 最小值为 w，那么 Alice 一定会进货所有 b_i \le w 的物品。

因此我们按照 b_i 排序，枚举 w，预处理所有 b_i \le w 的物品的贡献，对于 b_i > w 的物品，选择其中 a_i 前 k 小的物品一定是最优的，这容易用堆动态维护。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
struct node{
    int a,b;
}d[N];
int T,n,k,num,sum[N],ans;
priority_queue<int>q;
bool cmp(node x,node y){
    return x.b<y.b;
}
int read(){
    int k=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9')
        k=k*10+ch-'0',ch=getchar();
    return k;
}
signed main(){
    T=read();
    while(T--){
        n=read(),k=read();
        ans=0;
        for(int i=1;i<=n;i++)
            d[i].a=read();
        for(int i=1;i<=n;i++)
            d[i].b=read();
        sort(d+1,d+1+n,cmp);
        for(int i=1;i<=n;i++){
            sum[i]=sum[i-1];
            if(d[i].a<d[i].b)
                sum[i]+=d[i].b-d[i].a;
        }
        num=0;
        for(int i=n;i>=1;i--){
            if(i<=n-k){
                ans=max(ans,sum[i]-num);
                q.push(d[i].a);
                num+=d[i].a-q.top();
                q.pop();
            }
            else{
                num+=d[i].a;
                q.push(d[i].a);
            }
        }
        printf("%lld\n",ans);
        while(!q.empty())
            q.pop();
    }
    return 0;
}