经过∞次TLE
原题链接：35.[CSP-J 2020] 直播获奖
2025-07-19 11:11:29
发布于：北京
40阅读
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;
}
第二次：
桶排序吧
#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;
}
第三次：
从最大值向下找
#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;
}
老实了。。。
读到这里有福了，以下是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;
}
有帮助，赞一个