直播 获奖（live）

题目链接：https://www.luogu.com.cn/problem/P7072

方法一：50分代码（时间复杂度为n*nlongn）

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, w, a[100010], b[100010], p;
 4 bool cmp(int x, int y){
 5     return x>y;
 6 }
 7 int main(){
 8     cin>>n>>w;
 9     for(int i=0; i<n; i++){
10         cin>>a[i];
11         sort(a, a+i+1, cmp);//sort时间复杂度为nlogn  
12 //        for(int j=0; j<=i; j++)cout<<a[j]<<" ";
13 //        cout<<endl;
14         p=max(1, (i+1)*w/100);
15         cout<<a[p-1]<<" ";
16     }
17     return 0;
18 }

方法二：计数排序（时间复杂度为ns=O(100000600)）但仍然是85分，原因是第15行处没有必要增加一层循环

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, w, score, a[605], p;
 4 int main()
 5 {
 6     cin>>n>>w;
 7     for(int i=1; i<=n; i++){
 8         cin>>score;
 9         a[score]++;
10         p=max(1, i*w/100);
11         for(int s=605; s>=0; s--){
12             if(a[s]){
13                 int t=a[s];//临时存放该分数出现的次数，下次还要使用
14                 int f=0;//判读是否达到排名位数
15                 while(t--){
16                     p--;
17                     if(p==0){
18                         f=1;
19                         break;
20                     }    
21                 }
22                 if(f){
23                     cout<<s<<" ";
24                     break;
25                 }
26             }
27         }    
28     }
29     return 0;
30  }

方法三：其实是对方法二的优化

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, w, x, a[607];
 4 int main() {
 5     scanf("%d%d", &n, &w);
 6     for(int i = 1; i <= n; ++i) {
 7         scanf("%d", &x);
 8         a[x]++;
 9         int pl = max(1, i * w / 100);//获奖人数 
10         int num = 0;//记录当前排名次 
11         for(int j = 600; j >= 0; --j) {
12             num += a[j];
13             if(num >= pl) {
14                 printf("%d ", j);//循环结束条件 
15                 break;
16             }
17         }
18     }
19     return 0;
20 }

原文链接: https://www.cnblogs.com/tflsnoi/p/13947516.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍