AT1207 説明会 题解
题目传送门
更好的阅读体验？
我的思路：
-
考了
0 分的选手不能参加面试，可以直接跳过。 -
其余选手的分数用数组存储，
n 个分数全部输入后，将数组内的分数排序，方便以后进行分数线的判断。 -
在输入会场的最大可容纳人数的同时计算分数线，可以减少
O(q) 的时空复杂度。 -
当计算分数线时，有以下两种情况：
面试会场可容纳所有分数不为零的选手，此时的分数线是
0 ，代码实现为if(k>=tot) cout<<0<<endl;；面试会场容纳不下所有分数不为零的选手，分情况讨论：
分数线及以上的选手正好为
k_i ，此时分数线最低为低于分数线选手的最高分加1 。分数线及以上的选手低于
k_i ，不能再降低分数线，此时分数线最低为低于分数线选手的最高分加1 。
得通项公式：低于分数线选手的最高分加
1 ，又因为是从小到大排序，所以，代码实现为else cout<<a[tot-k]+1<<endl;。注：
a[tot-k+1]为会场正好满时最低的分数，此时低于分数线选手的最高分为a[tot-k]，分数线应为a[tot-k]+1。数据在
\operatorname{int} 范围内。
- 在
\operatorname{sort} 排序时，最坏情况下，时间复杂度为O(n^2+n+q) ，不能通过本题，需要考虑归并排序，原理就不细讲了，不懂可以百度，并且可以做一下模板题。
最坏情况下的复杂度：
时间：
空间：
sort代码：
#include<bits/stdc++.h> //万能头文件
using namespace std;
int n,q,a[100005],k,tot;
//tot为分数不为零的选手的数量
int main()
{
cin>>n;//n个选手
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(x==0) continue;//分数等于零时跳过
else
{
tot++;
a[tot]=x;
}//等于 a[++tot]=x;
}
sort(a+1,a+tot+1);//sort默认由小到大排序
cin>>q;//q次询问
for(int i=1;i<=q;i++)
{
cin>>k;
if(k>=tot) cout<<0<<endl;//套公式
else cout<<a[tot-k]+1<<endl;//套公式
}
return 0;
}归并排序代码:
#include<bits/stdc++.h> //万能头文件
using namespace std;
int n,q,a[100005],k,tot;
//tot为分数不为零的选手的数量
int t[100005];
void mergesort(int l,int r)//归并板子，可以背一下
{
if(l==r) return;
int mid=(l+r)/2;
//等价于 int mid=(l+r)>>1;
mergesort(l,mid);
mergesort(mid+1,r);
int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r)
{
if(a[i]<a[j]) t[k++]=a[i++];
else t[k++]=a[j++];
}
while(i<=mid) t[k++]=a[i++];
while(j<=r) t[k++]=a[j++];
for(i=l;i<=r;i++) a[i]=t[i];
return;
}
int main()
{
cin>>n;//n个选手
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(x==0) continue;//分数等于零时跳过
else
{
tot++;
a[tot]=x;
}//等于 a[++tot]=x;
}
mergesort(1,max(tot,1));//改成归并排序
//可能tot为0，这时会RE，需要和1取最大值。
cin>>q;//q次询问
for(int i=1;i<=q;i++)
{
cin>>k;
if(k>=tot) cout<<0<<endl;//套公式
else cout<<a[tot-k]+1<<endl;//套公式
}
return 0;
}