经过∞次TLE

原题链接：35.[CSP-J 2020] 直播获奖

skirmish

2025-07-19 11:11:29

发布于：北京

68阅读

0回复

0点赞

第一次：
每次加一个人的分，sort一下不就行了吗
~~13行秒了~~

#include <bits/stdc++.h>
using namespace std;
int n,w,p;
int a[100005];
int main(){
    cin>>n>>w;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        sort(a+1,a+i+1,greater<int>());//这里超时
        cout<<a[max(1,i*w/100)]<<' ';
    }
    return 0;
}

$\Large\tt{TLE}$

第二次：
桶排序吧

#include <bits/stdc++.h>
using namespace std;
int n,w;
int a[100005],_sort[605];
int main(){
    cin>>n>>w;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        _sort[a[i]]++;
        int j=600;
        int p=0;
        while (p<max(1,i*w/100)){//脑子抽了不知道为啥用while
            int x=_sort[j];
            while (p<max(1,i*w/100)&&x>0){
                p++;
                x--;
            }
            j--;
        }
        cout<<j+1<<' ';
    }
    return 0;
}

$\Large\tt{DOUBLE\ TLE}$

第三次：
从最大值向下找

#include <bits/stdc++.h>
using namespace std;
int n,w,mx;
int a[100005],_sort[605];
int main(){
    cin>>n>>w;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        if (a[i]>mx) mx=a[i];
        _sort[a[i]]++;
        int j=mx;
        int p=0;
        while (p<max(1,i*w/100)){//DOUBLE 脑子抽
            int x=_sort[j];
            while (p<max(1,i*w/100)&&x>0){
                p++;
                x--;
            }
            j--;
        }
        cout<<j+1<<' ';
    }
    return 0;
}

$\Large\tt{TRIPLE\ TLE}$

老实了。。。

读到这里有福了，以下是AC代码：

#include <bits/stdc++.h>
using namespace std;
int n,w;
int a[100005],_sort[605];
int main(){
    cin>>n>>w;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        _sort[a[i]]++;
        int cnt=0;
        for (int j=600;j>=0;j--){//for比while快
            cnt+=_sort[j];
            if (cnt>=max(1,i*w/100)){
                cout<<j<<' ';
                break;
            }
        }
    }
    return 0;
}