直播获奖 题解 FROM CSDN

讲解

好好审审这题，不难发现，输出即时的分数线肯定是输入一个数就输出一个数，而不是全部输完在统一输出，所以不难想出一种算法：先输入，接着存入数组里，接着按降序排一下序，最后输出最后一个获奖的人。

错误代码:

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,w,a[100005],m;
	cin>>n>>w;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		m=max(1,i*w/100);
		sort(a,a+i,greater<int>());
		cout<<a[m]<<" ";
	}
	return 0;
}

但是我们会发现,这样的代码只能获得50分,很明显,原因是TLE(超时),因为log时间复杂度是$n$x $log_2(n)$,再乘外部的$n$,整个时间复杂度是$n^2$x $log_2(n)$,$n$最大1000,$log_2(10000)$大概是在13~14左右,$10^4$的平方x13已超过$10^8$所以会TLE(超时),我们应该优化,换一个新的算法。

看来我们不能用数组来分别存每个人的成绩，那么还有什么办法呢？一定是我们忽略了什么关键信息，然后我们会发现一条至关有用的信息：对于所有测试点，每个选手的成绩均为不超过 600 的非负整数，因为成绩共有600个值，那我们不妨存一个下标有600的数组，每个元素存下标的人数。输入完成绩过后，就把下标为输入的数的元素加一，然后从600到0进行一次循环，再定义一个累加的变量，将每个元素的值加入，如果获奖人数大于或等于（因为有可能分数线上有许多人）预期的获奖人数，就输出下标并结束循环。
这道题其实不难，主要的问题是解决超时的问题，解决超时的问题的办法就是优化

最终代码+注释

#include<bits/stdc++.h>
using namespace std;
int main(){
	int x,a[605]={0},n,w,sum;
	cin>>n>>w;//输入人数和获奖率
	for(int i=1;i<=n;i++){//循环输入
		cin>>x;//输入分数
		a[x]++;//将得x分的人加一
		sum=0;//先将获奖的人数置为0
		for(int j=600;j>=0;j--){//计算最后一名获奖的人考了多少分
			sum+=a[j];//从高到低计算人数
			if(sum>=max(1,i*w/100)){//直到获奖的人数足够
				cout<<j<<' ';//输出最后一个获奖的分数
				break;//提前结束循环
			}
		}
	}
	return 0;
}

欢迎加入团队