题解：P15543 [CCC 2026 S4] Minecarts

· · 题解

曾经居然有紫。

考虑先分析假设我们已经知道了分配的方式，答案是多少：先假设是一个排列，对于最大的一个数 a_i，显然至少要有 n - i 个位置；对于第二大的数 a_j，如果它在 i 之前，就是 n - j - 1，否则就是 n - j。很容易发现其实就是每个位置的逆序对的数量的最大值。

接下来容易发现是可以二分答案的，考虑怎样 check 一个答案：考虑先计算出 nxt_i 和 cnt_i 表示以 i 第一个的逆序对数和 i 之后的 0 的数量，那么我们需要修改的位置就有 cnt_i - (x - nxt_i) 个。考虑从大到小依次访问每一个非 0 的位置，那么显然修改一段后缀是最优的，因为这样做既可以满足自己的限制，也可以满足其他位置的需求。所以在每个位置打个标记，最后顺序扫一遍即可得到每一个 0 最后是多少。代码为了方便是按照倒序实现的。

代码：

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
const int N = 1e6 + 5;

bool bst;
int n,k;
int a[N];
int cnt[N],nxt[N];
namespace BIT{
    #define lbt(x) (x & -x)
    int tr[N];
    void insert(int x,int val){for (int i = x;i <= 1000000;i += lbt(i)) tr[i] += val;}
    int query(int x){int res = 0;for (int i = x;i;i -= lbt(i)) res += tr[i];return res;}
}using namespace BIT;
pii b[N];int tot;
int c[N];
bool check(int x){
    for (int i = 1;i <= cnt[1];i++) c[i] = 0;
    for (int i = 1;i <= tot;i++){
        if (nxt[b[i].se] > x) return 0;
        if (nxt[b[i].se] + cnt[b[i].se] <= x) continue;
        int num = cnt[b[i].se] - (x - nxt[b[i].se]);
        c[num] = max(c[num],b[i].fi);
    }
    int nw = 0,sum = 0;
    for (int i = cnt[1];i >= 1;i--) nw = max(nw,c[i]),sum += nw;
    return (sum <= k);
}
bool bed;
signed main(){
//  freopen("subtask6_sample.in","r",stdin);
    //freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n >> k;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = n;i >= 1;i--){
        cnt[i] = cnt[i + 1];
        if (a[i] == 0) cnt[i]++;
        else{
            nxt[i] = query(a[i] - 1);
            insert(a[i],1);
            b[++tot] = {a[i],i};
        }
    }sort(b + 1,b + 1 + n,greater<pii>() );
    int l = 0,r = n,mid,res = n - 1;
    while (l <= r){
        mid = (l + r) >> 1;
        if (check(mid)) res = mid,r = mid - 1;
        else l = mid + 1;
    }cout << res << "\n";
    return 0;
}
/*
10 1875321
0 909971 857006 965351 653845 0 758384 906327 0 78343

*/