题解：AT_arc186_c [ARC186C] Ball and Box

· · 题解

前言

好题好题。

题解

首先我们先确定双方的策略。

当 n < m 时，B 最多接受 n 种颜色的小球，如果 A 再给他一个其他颜色的，他将无法购买，又因为 1 \le P_i \le 10^9，所以此时最大收益为 0，即一开始就结束游戏。

接下来我们讨论的都是 n \ge m 的情况。

对于 A 来说，他想让 B 多花钱，那么肯定想让他多买盒子。

因为有一个盒子必须放同种颜色小球的要求，所以 A 肯定先是每种颜色的小球都给一个。

此时 B 已经有了 m 个盒子。

为了延续一开始的策略，假设此时 B 容量最小的盒子为 p ，那么 A 肯定是不断给 B 与盒子 p 中小球颜色相同的小球，从而把 p 装满。

那么剩下 m-1 个盒子中肯定都只有一个小球。

这 m-1 个盒子的总花费为 \sum (1-P_i)。

把 p 装满后，B 还可以购入新的盒子，每个新的盒子的得分都是 V_i-P_i ，又因为 B 可以在任意时刻结束游戏，所以也可以不购入，此时每个盒子的价值都为 \max(0,V_i-P_i)。

简单分析过后我们来计算答案。

因为我们对购买的盒子中容量前 m-1 大的盒子与其他的盒子的得分的计算不一样。所以我们要先对 V_i 降序排序。

我们可以枚举分界点 pos ，在 pos 前面选出 m-1 个盒子。

购入的新的盒子的得分转化为一段后缀，记 suf_i 表示在 i 及以后选“新的盒子“的得分。

suf_i = \sum_{i}^{n} \max(0,V_i-P_i)

需要最大化得分，意味着我们在 pos 前要选 m-1 个最小的 P_i，我用了权值线段树来维护。

时间复杂度 \mathcal{O}(n \log V)。（V 为值域）

talk is cheap, show me the code!

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
int T,n,m;
ll suf[N];
struct Box{
    int v,p;
    void get(){
        scanf("%d %d",&v,&p);
    }
    bool operator < (const Box &qwq) const{
        return (v==qwq.v?p<qwq.p:v>qwq.v);//在v相同时先选p小的。
    }
}a[N];
namespace SegTree{//动态开点线段树
    int tot=0,rt=0;
    struct node{
        int ls,rs;
        int cnt;
        ll val;
    }tr[N<<5];//注意线段树节点个数是 O(n log V) 的。
    void pushu(int p){
        tr[p].cnt=tr[tr[p].ls].cnt+tr[tr[p].rs].cnt;
        tr[p].val=tr[tr[p].ls].val+tr[tr[p].rs].val;
    }
    void upd(int &p,int l,int r,int x){
        if(!p){
            p=++tot;
            tr[p].ls=tr[p].rs=tr[p].cnt=tr[p].val=0;
            //清空。
        }
        if(l==r){
            tr[p].cnt++;
            tr[p].val=1ll*x*tr[p].cnt;
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid)  upd(tr[p].ls,l,mid,x);
        else upd(tr[p].rs,mid+1,r,x);
        pushu(p);
    }
    ll qry(int p,int l,int r,int x){//查询前x大
        if(!p)  return 0ll;
        if(tr[p].cnt<=x)    return tr[p].val;
        if(l==r){
            return tr[p].val;
        }
        ll res=0ll;
        int mid=(l+r)>>1;
        if(tr[tr[p].ls].cnt>=x) return qry(tr[p].ls,l,mid,x);
        res=tr[tr[p].ls].val+qry(tr[p].rs,mid+1,r,x-tr[tr[p].ls].cnt);
        return res;
    }
}using namespace SegTree;
void sol(){
//  cerr<<"new case:";
    scanf("%d %d",&n,&m);

    for(int i=1;i<=n;i++){
        a[i].get();
    }
    if(n<m||m==0){//注意特判。
        printf("0\n");
        return;
    }
    sort(a+1,a+n+1);
    suf[n+1]=0ll;
    for(int i=n;i>=1;i--){
        ll qwq=max(0ll,(ll)(a[i].v-a[i].p));
        suf[i]=suf[i+1]+qwq;
    }
    if(m==1){
        //因为此时 A 只能给一种球，所以没有选 m-1 个容量最大的盒子这一步骤，直接跳到后面的一步。
        printf("%lld\n",suf[1]);
        return;
    }
    ll ans=-1e15;//答案一开始取极小值。
    tot=rt=0;//清空。
    for(int i=1;i<=n;i++){
        upd(rt,1,1e9,a[i].p);
        if(i<m-1)   continue;//至少加入m-1个。
        ll sump=qry(rt,1,1e9,m-1);
        ll res=m-1-sump;//有 m-1 个 (1-P_i)
        ans=max(ans,res+suf[i+1]);
    }
    printf("%lld\n",max(ans,0ll));//和一开始就结束游戏的情况取max
}
signed main(){
//  freopen("test.in","r",stdin);
//  freopen("my.out","w",stdout);
    scanf("%d",&T);
    while(T--) sol();
    return 0;
}