P9636 题解

· · 题解

题意

题意是给定五个正整数 n,m,k,l,r，然后输入长度为 n 的数组，对于任意的 i\geq k，该题目的可做性为 1\sim i 题难度值从大到小排序后难度最大的 k 道题目难度之和。然后你可以篡改第 m 道题的难度，尝试使所有题目的可做性之和控制在 l\sim r 之间。试求满足该条件下，最大的所有题目的可做性之和。若无法满足，输出 -1。

思路

看上去像是二分，只需二分第 m 道题的难度，然后计算出这种情况下所有题目的可做性之和是否满足条件即可。但是问题在于计算每一道题的可做性。如果按照题意来，枚举出所有题目，则需 O(n^2) 的时间复杂度，乘上二分的 O(\log n)，肯定爆。

其实我们可以借用第 i 道题目的可做性来推导第 i+1 道题目的可做性。如果第 i+1 道题目的难度比之前的所有题目难度都低，那只能是前一道题目的可做性，因为最难的 k 道题不变。如果不是，那么只需要踢掉前面题目中最简单的那个，然后把这题的难度加上，就是最难的 k 道题。对于记录前面最简单的题，可以用优先队列维护，对于可做性和难度，可以用数组维护。时间复杂度大约为 O(n\log n\log V)，足以通过本题。

注意：数据有些大，需要开 64 位。

代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100005;
ll i,j,n,m,k,r,l,cur,all,nandu[N],kezuoxing[N];
priority_queue<ll,vector<ll>,greater<ll> > q;

ll build(){
    ll i,cnt=0,all=0;
    for(i=1;i<=k;i++){
        cnt+=nandu[i];
        q.push(nandu[i]);
    }
    kezuoxing[k]=cnt;
    all+=cnt;
    for(i=k+1;i<=n;i++)
    {
        if(nandu[i]>q.top()){
            cnt-=q.top();
            q.pop();
            cnt+=nandu[i];
            q.push(nandu[i]);
        }
        kezuoxing[i]=cnt;
        all+=cnt;
    }
    return all;
}

ll binsch(){//二分查找 
    ll lastpos=-1;
    long long right=100000005,left=1,mid;
        while(left<=right)
        {
            mid=right-(right-left)/2;
            while(!q.empty()) q.pop();//清空优先队列
            nandu[m]=mid;//篡改数据
            ll tri=build();//生成可做性 
            if(l<=tri&&r>=tri){
                lastpos=max(lastpos,tri);
                left=mid+1;
            }
            else if(l>tri) left=mid+1;
            else right=mid-1;
        }
    return lastpos;
}
int main(){

    cin>>n>>m>>k>>l>>r;
    for(i=1;i<=n;i++) cin>>nandu[i];//输入数据 
    cout<<binsch();
    return 0;
}