#include<iostream> #include<cmath> #include<algorithm> #include<cstdio> using namespace std; int bucket[605]; int main(){ int n,s; double w; scanf("%d%lf",&n,&w); for(int i=1;i<=n;i++){ scanf("%d",&s); bucket[s]++; int q=i*w/100; int k=max(1,q),num=0,flag=0; for(int j=600;j>=0;j--){ num+=bucket[j]; if(num>=k){ cout<<j<<" "; break; } } } return 0; }

讲解 好好审审这题，不难发现，输出即时的分数线肯定是输入一个数就输出一个数，而不是全部输完在统一输出，所以不难想出一种算法：先输入，接着存入数组里，接着按降序排一下序，最后输出最后一个获奖的人。 错误代码: 但是我们会发现,这样的代码只能获得50分,很明显,原因是TLE(超时),因为log时间复杂度是nnnx log2(n)log_2(n)log2 (n),再乘外部的nnn,整个时间复杂度是n2n^2n2x log2(n)log_2(n)log2 (n),nnn最大1000,log2(10000)log_2(10000)log2 (10000)大概是在13~14左右,10410^4104的平方x13已超过10810^8108所以会TLE(超时),我们应该优化,换一个新的算法。 看来我们不能用数组来分别存每个人的成绩，那么还有什么办法呢？一定是我们忽略了什么关键信息，然后我们会发现一条至关有用的信息：对于所有测试点，每个选手的成绩均为不超过 600 的非负整数，因为成绩共有600个值，那我们不妨存一个下标有600的数组，每个元素存下标的人数。输入完成绩过后，就把下标为输入的数的元素加一，然后从600到0进行一次循环，再定义一个累加的变量，将每个元素的值加入，如果获奖人数大于或等于（因为有可能分数线上有许多人）预期的获奖人数，就输出下标并结束循环。 这道题其实不难，主要的问题是解决超时的问题，解决超时的问题的办法就是优化 最终代码+注释 欢迎加入团队

其实我们只要观察一下数据范围就会发现，分数的范围非常小！（只有600） 于是就顺理成章的想到了桶排。 思路非常简单，而且不存在超时。

666也是用上高科技(指lower_bound函数)了

其实可以用桶排序做：

#include <bits/stdc++.h> using namespace std; int bucket[605]; int main(){ int n,s; double w; scanf("%d%lf",&n,&w); for(int i=1;i<=n;i++){ scanf("%d",&s); bucket[s]++; int q=i*w/100; int k=max(1,q),num=0,flag=0; for(int j=600;j>=0;j--){ num+=bucket[j]; if(num>=k){ cout<<j<<" "; break; } } } return 0; }

*2023-08-18 恭喜你，提交通过！ 执行用时：22ms 内存消耗：1.97MB 击败了100.00%的用户 击败了0.00%的用户 #include <bits/stdc++.h> using namespace std; priority_queue<int> ma_hp; priority_queue<int, vector<int>, greater<int> > mi_hp; int n, w, now, num; void qwq() { if (mi_hp.size()<now) { mi_hp.push(ma_hp.top()); ma_hp.pop(); } if (mi_hp.size() > now) { ma_hp.push(mi_hp.top()); mi_hp.pop(); } } void push(int num) { if (num >= ma_hp.top()) mi_hp.push(num); else ma_hp.push(num); qwq(); } int main() { scanf("%d%d", &n, &w); ma_hp.push(0); for (int p = 1; p <= n; p++) { now=max(1,p*w/100); scanf("%d", &num); push(num); printf("%d ", mi_hp.top()); } return 0; }

用桶排序

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

//CSP-J2 2020第2题 live 直播获奖 #include<iostream> #define int long long using namespace std; const int MAXN=605; int n,w,target,a[MAXN]; void check(int p){ int num=0,cnt=0,ans=0; num=p*w/100; cnt=max(1LL,num); //max(a,b)中 a与b的类型需要一致，"1LL"表示long long类型的1,与long long类型的num一致 for(int i=600;i>=0;i--){ if(cnt>=1&&a[i]>0){ ans=i; cnt-=a[i]; } } cout<<ans<<" "; return; } signed main(){ // freopen("live.in","r",stdin); // freopen("live.out","w",stdout); cin>>n>>w; for(int i=1;i<=n;i++){ cin>>target; a[target]++; check(i); } // fclose(stdin); // fclose(stdout); return 0; }

C版： #include<cmath> #include<algorithm> using namespace std; int a[601]; int main(){ int n,w; cin>>n>>w; for(int i=1;i<=n;i){ int x; cin>>x; a[x]++; int s=max(1,i*w/100); long long sum=0; for(int j=600;j>=0;j--){ sum+=a[j]; if(sum>=s){ cout<<j<<" "; break; } } } return 0; }

#include<bits/stdc++.h> using namespace std; int bucket[605]; int main(){ int n,s; double w; scanf("%d%lf",&n,&w); for(int i=1;i<=n;i++){ scanf("%d",&s); bucket[s]++; int q=i*w/100; int k=max(1,q),num=0,flag=0; for(int j=600;j>=0;j--){ num+=bucket[j]; if(num>=k){ cout<<j<<" "; break; } } } return 0; }

#include <iostream> #include <algorithm> using namespace std; int a[610]; int main(){ int n, w; cin >> n >> w; }

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

#include<bits/stdc++.h> using namespace std; int main(){ int x,a[610]={},n,w,sum; cin>>n>>w; for(int i=1;i<=n;i++){ cin>>x; //输入n个数 a[x]++; sum=0; //给sum初始值 for(int j=600;j>=0;j--){ sum+=a[j]; if(sum>=max(1,i*w/100)){ //判断 cout<<j<<' '; break; //输出并跳出 } } } return 0; //结束 }