题解 | #和+和#

如果写过练习赛134的B题，你会很容易想到思路，完全可以借鉴

• 用一个数组记录a数组的前i项中m个数和的最小值
• 用一个数组记录b数组的后i项中m个数和的最小值

记录时，用一个优先队列，始终保持其中有m个数，往后取一个数如果比其中最大的数小，就踢出，并替换

根据题目条件，a选取最后一个数的下标不能比b数组选取的第一个数的下标更大 所以

#include<bits/stdc++.h>

using namespace std;
#define ll long long 
int n,m;
const int maxn=2e5+10;
int a[maxn],b[maxn];
ll mina[maxn],minb[maxn];
priority_queue<int>q;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n;++i) cin>>b[i];
    ll sum=0;
    for(int i=1;i<=n-m;++i){
        if(i<=m){
            q.push(a[i]);
            sum+=a[i];
        }
        else {
            if(a[i]<q.top()){
	            sum-=q.top();
	            q.pop();
	            q.push(a[i]);
	            sum+=a[i];
			}
            
        }
        if(i>=m){
            mina[i]=sum;
        }
    }
    while(!q.empty()) q.pop();
    sum=0;
    for(int i=n;i>m;--i){
        if(n-i+1<=m){
            q.push(b[i]);
            sum+=b[i];
        }
        else {
            if(b[i]<q.top()) {
	            sum-=q.top();
	            q.pop();
	            q.push(b[i]);
	            sum+=b[i];
			}
            
        }
        if(n-i+1>=m){
            minb[i]=sum;
        }
    }
    ll ans=1e18;
    for(int i=m;i<=n-m;++i){
        ans=min(ans,mina[i]+minb[i+1]);
    }
    cout<<ans<<endl;
}