题解 | #和+和#

数据结构爱好者来一个E的思路。
从 到 枚举分界点。
用一个大根堆来存储 选中的数，移动过程中只要新数大于堆顶的数就替换。
标记一下 选择了的下标，用一个小根堆来存储 还没被选的数的下标，一旦 有数在范围外被踢走了，就从小根堆里面挑最小的合法的替换掉。

#include <bits/stdc++.h>
#define int long long
#define inf 2e18
#define ull unsigned long long
#define ls o << 1
#define rs o << 1 | 1

using namespace std;
const int N = 2e5 + 9;
int a[N], b[N];
bool vis[N];

struct mypq {
    bool operator () (const int &u, const int &v) {
        return b[u] > b[v];
    }
};

void solve()
{
    int n, m;cin >> n >> m;
    for(int i = 1;i <= n;i ++)cin >> a[i];
    for(int i = 1;i <= n;i ++)cin >> b[i];

    priority_queue<int> A;
    int sum = 0;
    int ans = inf;

    for(int i = 1;i <= m;i ++) {
        sum += a[i];
        A.push(a[i]);
    }

    priority_queue<int, vector<int>, mypq> B;

    vector<pair<int, int>> c;

    for(int i = m + 1;i <= n;i ++) {
        c.push_back({b[i], i});
    }

    sort(c.begin(), c.end());

    for(int i = 0;i < c.size();i ++) {
        if(i < m) {
            sum += c[i].first;
            vis[c[i].second] = true;
        } else {
            B.push(c[i].second);
        }
    }

    ans = min(ans, sum);

    for(int i = m + 1;i <= n - m;i ++) {
        if(A.size() && a[i] < A.top()) {
            sum -= A.top();
            sum += a[i];
            A.pop();
            A.push(a[i]);
        }

        if(vis[i]) {
            while(B.size() && B.top() <= i) {
                B.pop();
            }

            if(B.size()) {
                sum -= b[i];
                vis[B.top()] = true;
                sum += b[B.top()];
                B.pop();
            }
        }

        ans = min(ans, sum);
    }

    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    int t = 1;//cin >> t;
    while(t --)solve();

    return 0;
}


/*
What you want is what you love, so fight for it!
*/