TLE85分求优化

常规
1

题目：CSP2020-J-2-直播获奖

#include<bits/stdc++.h>
using namespace std;
int read(){
  int a=0;
  char c=getchar();
  while(c>='0'&&c<='9'){
    a=a*10+c-'0';
    c=getchar();
  }return a;
}int main(){
  freopen("live.in","r",stdin);
  freopen("live.out","w",stdout);
  int n,a,f[610],w;
  vector<int>v;
  memset(f,0,sizeof(f));
  ios::sync_with_stdio(false);
  n=read();
  w=read();
  for(int i=1;i<=n;i++){
    a=read();
    f[a]++;
    for(int j=600;j>=0;j--){
      for(int k=0;k<f[j];k++)v.push_back(j);
    }cout<<v[(i*w/100<1?0:i*w/100-1)]<<" ";
    v.clear();
  }return 0;
}
2

建议开两个优先队列，一个大根堆，一个小根堆，把前w%扔进小根堆，剩余的和从小根堆中被挤出来的放入大根堆，当小根堆可以放数时（前w%人数不够或者大根堆的顶端比小根堆的top大时，小根堆的top放入大根堆，大根堆的top扔进小根堆

1 个赞
3

桶排序变形题，逐行输出，排序

1 个赞
4

没那么复杂，用桶，每次求桶中所有元素数量，如果 ans \ge \max(1,i*w/100) ，输出 j 即可。

for(int j=600;j>=0;j--){
	ans+=c[j];
	if(ans>=max(1,i*w/100)){
	    cout<<j<<' ';
	    break;
	}
}
2 个赞
5

对顶堆是这样的：

if(max(1,i*w/100)>cnt||q.empty()) q.push(pq.top()),pq.pop(),cnt++;
else if(pq.top()>q.top()){
       	pq.push(q.top());
       	q.pop();
       	q.push(pq.top());
     	pq.pop();
}
6

太可恶了，a[i]要是更大就只能用对顶堆了

7

都可以

8