自动搬运

查看原文

来自洛谷，原作者为

	oMin0 oahzgnim| 悲欢离合总无情，一任阶前点滴到天明

搬运于2025-08-24 23:00:52，当前版本为作者最后更新于2024-07-11 09:23:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

建议降蓝。

分析

首先警示后人，题目并不要求你按照 $1\sim n$ 的顺序依次操作，你可以按任意顺序做选择，感觉它没说明白。

考虑这样一件事情，假如我们盗窃了 $i$，然后用 $j$ 取消仇恨，那么最优策略必然满足 $m_i-p_j\geq m_j-p_i$，否则可以交换对这两人执行的操作。

这意味着按照 $m_i+p_i$ 排序后，被盗窃的人家和被贿赂的人家存在一个分界点。我们枚举分界点，那然后一定是对前缀 $m_i$ 的前 $k$ 大盗窃，并给后缀 $p_i$ 的前 $k$ 小送钱。用二分+主席树即可做到 $O(n\log^2 n)$，不过更好写的办法是先二分答案 $ans$，然后用堆维护固定 $k$ 的前 $k$ 小信息，具体实现见代码。

代码

/*
  author: honglan0301
  Sexy_goodier _ xiaoqing
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <queue>
using namespace std;
#define int long long
#define endl "\n"

int n,m[100005],p[100005],bh[100005];
bool cmp(int x,int y) {return m[x]+p[x]>m[y]+p[y];}

int sumq[100005],sumh[100005];
bool ck(int k)
{
	priority_queue <int,vector<int>,greater<int>> Q;
	int ns=0;
	for(int i=1;i<=n;i++)
	{
		if(Q.size()<k) Q.push(m[bh[i]]),ns+=m[bh[i]];
		else 
		{
			int nr=Q.top(); ns-=nr; Q.pop(); ns+=max(nr,m[bh[i]]); Q.push(max(nr,m[bh[i]]));
		}
		sumq[i]=ns;
	//	cout<<i<<" "<<sumq[i]<<endl;
	}
	ns=0; while(!Q.empty()) Q.pop();
	for(int i=n;i>=1;i--)
	{
		if(Q.size()<k) Q.push(p[bh[i]]),ns+=p[bh[i]];
		else 
		{
			int nr=Q.top(); ns-=nr; Q.pop(); ns+=max(nr,p[bh[i]]); Q.push(max(nr,p[bh[i]]));
		}
		sumh[i]=-ns;
		//cout<<i<<" "<<sumh[i]<<endl;
	}
	for(int i=k;i+k<=n;i++) if(sumq[i]>=sumh[i+1]) return 1; return 0;
}

signed main()
{
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>m[i];
	for(int i=1;i<=n;i++) cin>>p[i];
	for(int i=1;i<=n;i++) bh[i]=i; sort(bh+1,bh+n+1,cmp);
	for(int i=1;i<=n;i++) p[i]=-p[i];
	int l=1,r=n/2;
	while(l<=r) {int mid=(l+r)>>1; if(ck(mid)) l=mid+1; else r=mid-1;} 
	cout<<r<<endl;
}