- xuorange 的博客
CF222D 题解
- 2022-5-28 11:21:23 @
首先,已知得分总分为至少k分,所以小A的得分是无上限的,所以很容易得知最好的名次是第一名。
所以我们要求的,就是最差的名次。只要将下面的两组分数加起来,看看最多可以有几组大于k就好了,组数就是小A的名次。
其次我们还要知道,要是所有的人成绩都一样,那么排名就是裁判员管的,我们只能是得到最后一名。
综上,使用贪心,a从小到大排序,b从大到小排序,如果a[i]+b[j]>k,那么名次+1,b的j+1;如果小于,那么无论如何,这个a加任何一个b都不会比小孩的分数高,所以用更大的a(为了贪心贪更多的名次,所以a从小到大排序)。
#include <iostream>
#include <algorithm>
using namespace std;
int a[100100],b[100100];
int n,k,ans=0;
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
ios::sync_with_stdio(false);//加速cin和cout
cin>>n>>k;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
cin>>b[i];
sort(a,a+n);//贪心
sort(b,b+n,cmp);
for(int i=0,j=0;i<n;i++)
{
if(a[i]+b[j]>=k)//等于的情况也是输
{
ans++;//计数
j++;//这个b使用之后,使用更小的b
}
}
cout<<"1 "<<ans<<endl;//1是白给的
return 0;
}