A – Larger Score

题目描述：

给定n个数，你可以交换任意相邻的两个数，使的原数组的前k个数字的和严格小于任意次交换后的前k个数字的和，问最小操作次数

思路：

其实就从[1,k]个数字中挑出来一个x，在[k+1,n]中选一个大于x的数字，问二者之间的最小距离

我们可以用二分来解决

将[k+1,n]中的数字升序排列，如果数字相同就按下标升序排列

从[1,k]中枚举i，二分第一个大于ar[i]的位置，根据我们的排序，这个位置后面的数都是大于ar[i]的，所以我们可以求一下这里面的下标的最小值，方法是开一个后缀最小值数组，这样就可以得到i的最小值，对所有的i取一个最小值就是答案

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 500000 + 50
int n, m, k;
int tr[MAX];
vector<pii>v;
int minx[MAX];

int erfen(int x){
    int l = 0, r = (int)v.size() - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if(v[mid].first > x)r = mid - 1;
        else l = mid + 1;
    }
    return l;
}

void work(){
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    for(int i = k + 1; i <= n; ++i){
        v.push_back(m_p(tr[i], i));
    }
    sort(v.begin(), v.end());
    minx[(int)v.size()] = inf;
    for(int i = (int)v.size() - 1; i >= 0; --i){
        minx[i] = min(minx[i + 1], v[i].second);
    }
    int ans = inf;
    for(int i = 1; i <= k; ++i){
        int p = erfen(tr[i]);
        if(p >= (int)v.size())continue;
        ans = min(ans, minx[p] - i);
    }
    if(ans == inf)cout << -1 << endl;
    else cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}