P7072 [CSP-J2020] 直播获奖 题解

· · 题解

这是本题已知最快的做法，时间复杂度：O(N\log V)。

云浅知处在他的题解里说：

然后就算是维护一下前缀和之后在树状数组上二分达到 O(n\log^2 600) 也大概有 O(49n)，所以我 BST 还是更快（

但是树状数组是可以倍增的，我们求出需要踢掉的人数，和别的题解一样设一个桶，只是这个桶是一个树状数组，然后倍增即可，很模板的一个倍增，注意一下符号是小于等于即可，和二分差距也不是很大，直接上代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define lowbit(x) ((x)&-(x))
int tree[1025],n,w,in1;
inline int gt(int p){
    return max(1,p*w/100);
}
void add(int x){
    x++;
    while(x<1025){
        tree[x]++;
        x+=lowbit(x);
    }
}
int getans(int p){
    int ti=0,wt=p-gt(p)/*要踢掉的人数*/,people=0;
    for(int j=9;j>=0;j--){
        if(people+tree[ti+(1<<j)]<=wt)ti+=(1<<j),people+=tree[ti];
    }
    return ti;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    cin>>n>>w;
    for(int i=1;i<=n;i++){
        cin>>in1;
        add(in1);
        cout<<getans(i)<<' ';
    }
}
#define IAKIOI 不要CV啊

这个代码的时间复杂度是 O(N\log V) 的，然后卡了卡常就轻松拿下了最优解。