题解 | #和+和#

E-和+和_牛客周赛 Round 82 先分析题意，我们知道我们可以找到a的前i项的的最小值和，由此，我们可以知道，可以预处理出两个数组，一个是a的前i项中m个数的最小和，另一个是b中从i到n中m个数的最小和，而想要维护出这两个数组，如果使用暴力遍历，那么找出一个完整的数组的复杂度是的极有可能超时，故我们可以使用优先队列，用top-k的思想来实现。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+9;
priority_queue<ll> pq;
ll prefix[N],back[N];//维护的两个数组
ll a[N],b[N];
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m;cin>>n>>m;
	ll ans=0x3f3f3f3f3f3f3f3f;
	ll res=0;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=m;i++){
		pq.push(a[i]);
		res+=a[i];
	}
	prefix[m]=res;
	for(int i=m+1;i<=n;i++){
		if(pq.top()>a[i]){
			int tmp=pq.top();
			pq.pop();
			pq.push(a[i]);
			prefix[i]=prefix[i-1]-tmp+a[i];
		}
		else{
			prefix[i]=prefix[i-1];
		}
	}
	while(!pq.empty()){
		pq.pop();
	}
	res=0;
	for(int i=n;i>n-m;i--){
		pq.push(b[i]);
		res+=b[i];
	}
	back[n-m+1]=res;
	for(int i=n-m;i>m;i--){
		if(pq.top()>b[i]){
			int tmp=pq.top();
			pq.pop();
			pq.push(b[i]);
			back[i]=back[i+1]-tmp+b[i];
		}
		else{
			back[i]=back[i+1];
		}
	}
	for(int i=m;i<=n-m;i++){
		ans=min(ans,prefix[i]+back[i+1]);//找到最小的值
	}
	cout<<ans;
	return 0;
}