题解：CF1969D Shop Game

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

CPP

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

题解：CF1969D Shop Game

文章操作

Description

Solution

Code

相关推荐

评论

题解：CF1969D Shop Game