自动搬运

查看原文

来自洛谷，原作者为

	metrixgo_caozhendi There‘s nothing left to say but I’m still here，…. ALIVE！！！

搬运于2025-08-24 22:50:18，当前版本为作者最后更新于2023-09-11 21:17:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

题意是给定五个正整数 $n,m,k,l,r$，然后输入长度为 $n$ 的数组，对于任意的 $i\geq k$，该题目的可做性为 $1\sim i$ 题难度值从大到小排序后难度最大的 $k$ 道题目难度之和。然后你可以篡改第 $m$ 道题的难度，尝试使所有题目的可做性之和控制在 $l\sim r$ 之间。试求满足该条件下，最大的所有题目的可做性之和。若无法满足，输出 $-1$。

思路

看上去像是二分，只需二分第 $m$ 道题的难度，然后计算出这种情况下所有题目的可做性之和是否满足条件即可。但是问题在于计算每一道题的可做性。如果按照题意来，枚举出所有题目，则需 $O(n^2)$ 的时间复杂度，乘上二分的 $O(\log n)$，肯定爆。

其实我们可以借用第 $i$ 道题目的可做性来推导第 $i+1$ 道题目的可做性。如果第 $i+1$ 道题目的难度比之前的所有题目难度都低，那只能是前一道题目的可做性，因为最难的 $k$ 道题不变。如果不是，那么只需要踢掉前面题目中最简单的那个，然后把这题的难度加上，就是最难的 $k$ 道题。对于记录前面最简单的题，可以用优先队列维护，对于可做性和难度，可以用数组维护。时间复杂度大约为 $O(n\log n\log V)$，足以通过本题。

注意：数据有些大，需要开 $64$ 位。

代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100005;
ll i,j,n,m,k,r,l,cur,all,nandu[N],kezuoxing[N];
priority_queue<ll,vector<ll>,greater<ll> > q;

ll build(){
	ll i,cnt=0,all=0;
	for(i=1;i<=k;i++){
		cnt+=nandu[i];
		q.push(nandu[i]);
	}
	kezuoxing[k]=cnt;
	all+=cnt;
	for(i=k+1;i<=n;i++)
	{
		if(nandu[i]>q.top()){
			cnt-=q.top();
			q.pop();
			cnt+=nandu[i];
			q.push(nandu[i]);
		}
		kezuoxing[i]=cnt;
		all+=cnt;
	}
	return all;
}

ll binsch(){//二分查找 
	ll lastpos=-1;
	long long right=100000005,left=1,mid;
		while(left<=right)
		{
			mid=right-(right-left)/2;
			while(!q.empty()) q.pop();//清空优先队列
		    nandu[m]=mid;//篡改数据
		    ll tri=build();//生成可做性 
			if(l<=tri&&r>=tri){
				lastpos=max(lastpos,tri);
				left=mid+1;
			}
			else if(l>tri) left=mid+1;
			else right=mid-1;
		}
	return lastpos;
}
int main(){
    
    cin>>n>>m>>k>>l>>r;
    for(i=1;i<=n;i++) cin>>nandu[i];//输入数据 
    cout<<binsch();
    return 0;
}