复赛2:直播获奖

洛谷:P7072

方法一:暴力50分

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
using namespace std;
int n,w;
int a[100010];

bool cmp(int x, int y){
   return x>y;
}

int main(){
    cin>>n>>w;
    for (int i = 1; i <=n; i++){
        cin>>a[i];
        sort(a+1,a+1+i,cmp);
        int p=max(1,i*w/100);
        cout<<a[p]<<" ";
    }
    return 0;
}

方法二:桶排序,满分

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**************************************************************** 
 * Description: 2020普及组复赛第2题,利用桶排序
 * Author: Alex Li
 * Date: 2023-10-20 11:59:48
 * LastEditTime: 2023-10-20 12:09:48
****************************************************************/
#include <iostream>
#include <algorithm>
using namespace std;
int n,w;
int a[1010]; //a[i]表示 得i分的同学有多少个。

int main(){
    cin>>n>>w;
    for (int i = 1; i <=n; i++){
       int x;
       cin>>x;
       a[x]++;
       int p=max(1,i*w/100);
       int sum=0;
       for(int j=600;j>=0;j--){
        if(sum+a[j]>=p){
            cout<<j<<" ";
            break;
        }
        sum+=a[j];
       }
    }
    return 0;
}
Scroll to Top