专栏文章

题解：AT_arc186_c [ARC186C] Ball and Box

cchaeminter2467
AT_arc186_c题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miq59fyq
此快照首次捕获于
2025/12/03 23:10
3 个月前
此快照最后确认于
2025/12/03 23:10
3 个月前
查看原文

前言

好题好题。

题解

首先我们先确定双方的策略。
当 n<mn < m 时，B 最多接受 nn 种颜色的小球，如果 A 再给他一个其他颜色的，他将无法购买，又因为 1≤Pi≤1091 \le P_i \le 10^9，所以此时最大收益为 00，即一开始就结束游戏。
接下来我们讨论的都是 n≥mn \ge m 的情况。
对于 A 来说，他想让 B 多花钱，那么肯定想让他多买盒子。
因为有一个盒子必须放同种颜色小球的要求，所以 A 肯定先是每种颜色的小球都给一个。
此时 B 已经有了 mm 个盒子。
为了延续一开始的策略，假设此时 B 容量最小的盒子为 pp ，那么 A 肯定是不断给 B 与盒子 pp 中小球颜色相同的小球，从而把 pp 装满。
那么剩下 m−1m-1 个盒子中肯定都只有一个小球。
这 m−1m-1 个盒子的总花费为 ∑(1−Pi)\sum (1-P_i)。
把 pp 装满后，B 还可以购入新的盒子，每个新的盒子的得分都是 Vi−PiV_i-P_i ，又因为 B 可以在任意时刻结束游戏，所以也可以不购入，此时每个盒子的价值都为 max⁡(0,Vi−Pi)\max(0,V_i-P_i)。
简单分析过后我们来计算答案。
因为我们对购买的盒子中容量前 m−1m-1 大的盒子与其他的盒子的得分的计算不一样。所以我们要先对 ViV_i 降序排序。
我们可以枚举分界点 pospos ，在 pospos 前面选出 m−1m-1 个盒子。
购入的新的盒子的得分转化为一段后缀，记 sufisuf_i 表示在 ii 及以后选“新的盒子“的得分。
sufi=∑inmax⁡(0,Vi−Pi)suf_i = \sum_{i}^{n} \max(0,V_i-P_i)
需要最大化得分，意味着我们在 pospos 前要选 m−1m-1 个最小的 PiP_i，我用了权值线段树来维护。
时间复杂度 O(nlog⁡V)\mathcal{O}(n \log V)。（VV 为值域）
talk is cheap, show me the code!

code

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...