CF802O 题解

· · 题解

提供一下不需要考虑网络流的思路。

主要思路：看到题中一个元素两种操作求最优联想到 CF865D Buy Low Sell High ，考虑这两道题之间的区别和联系。

第一个区别是 CF865D 中对股票的第二次操作为收益，本题中两次均为支出。

我们假设打印题目每道题花费上限为 M 元，则每次在第 i 天打印题目可视为节省（即收益） M - b_i 元。

将准备题目视为买入题目，打印视为卖出，运用 CF865D 中的方法，最后求出的答案 ans' 是：

ans' = \max \ \{\ \sum (M - b_{use}) - \sum a_{use}\ \}

运用这个我们可以 O(1) 求出要求的答案 ans（m 为选择题目个数）：

ans = \min \ \{\ \sum b_{use} + \sum a_{use}\ \} = M \times m \ -\ ans'

第二个区别是本题只能出刚好 m 道题。

考虑 CF865D 中两种极端情况，第一种是收益均为正无穷，显然买越多越好，第二种是收益均为负数，显然最好一个都不买。

感性理解一下，我们发现假如令所有股票的收益都加上 x，那么买的股票数是随 x 单调不减的。

而这种关系换到上面提出的做法就是求出最优解当中出题数随 M 单调不减。

那么我们二分 M ，找到刚好使最优解出题数为题中 m 的某个 M，再用它计算答案即可。

不过还需要考虑计算最优解出题数的方法。

在 CF865D 中，我们对于每一天会把两个价格丢进堆里，一次是买股票的支出，一次供反悔的卖股票的收入。

我们在把价格扔进堆里时多记录一个状态，若是真正买的则为 1，若是供反悔的则为 0。

每次取出堆顶时，若这个状态为 1，则给购买数（出题数）加一，反之不加，最后就得到了最优解购买数（出题数）。

代码： 

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn = 500005;

int n, m;
ll ans;
int a[maxn], b[maxn];
ll lb[maxn];
priority_queue <pair<ll, int> > que;

int read() {
    int x = 0, w = 1;
    char ch = 0;
    while (ch < '0' || ch > '9') {  
        if (ch == '-') w = -1;    
        ch = getchar();             
    }
    while (ch >= '0' && ch <= '9') { 
        x = x * 10 + (ch - '0'); 
        ch = getchar();  
    }
    return x * w; 
}

int check(ll tp)
{
    for(int i = 1; i <= n; i ++)
        lb[i] = tp - b[i];
    while(!que.empty()) que.pop();
    ans = 0;
    int cnt = 0;
    for(int i = 1; i <= n; i ++)
    {
        que.push({-a[i], 1});
        if(lb[i] > -que.top().first)
        {
            ans += lb[i] + que.top().first;
            cnt += que.top().second;
            que.pop();
            que.push({-lb[i], 0});
        }
    }
    ans -= 1ll * m * tp;
    return cnt;
}

int main()
{
    n = read(); m = read();
    for(int i = 1; i <= n; i ++)
        a[i] = read();
    for(int i = 1; i <= n; i ++)
        b[i] = read();
    ll l = 0, r = 20000000009;
    while(l < r)
    {
        ll mid = (l + r) >> 1;
        int res = check(mid);
        if(res == m)
        {
            r = mid;
            break;
        }
        else if(res > m)
            r = mid - 1;
        else l = mid + 1;
    } 
    check(r);
    cout<<-ans<<endl;
}