CF81C Average Score 题解

题目简述

给定一个长度为 $n$ 的序列，在其中取出 $x$ 个数，构成一个数列 $a$，剩下的 $y$ 个数构成数列 $b$。

若第 $i$ 个数在数列 $a$ 中，$ans_i$ 等于 $1$，否则等于 $2$，请你给出一种方案使得两数列的平均数之和最大且 $ans$ 的字典序最小.

题目分析

我们先考虑 $x=y$ 的情况，在这种情况下，对于第 $i$ 个数字，放入 $a$ 序列或者 $b$ 序列对答案的贡献都是一样的，由于字典序最小的要求，应优先将序号小的数放入 $a$ 序列中.

接下来考虑 $x$ 和 $y$ 不相等的情况，为了方便一些，我们令 $x \lt y$。对于一个数 $w$，它放入 $a$ 序列中对答案的贡献为 $\frac{w}{x}$，$b$ 序列中为 $\frac{w}{y}$，由于 $\frac{w}{y} \lt \frac{w}{x}$，所以它放入 $a$ 序列更优。

接下来，我们便有了贪心策略，将前 $x$ 大的数放入 $a$ 序列，剩余的放入 $b$ 序列，最后考虑一下字典序即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define random(a,b) (rand()%(b-a+1)+a)
const int N=1e5+1;
int n,x,y,T,ans[N];
struct Num
{
	int num,id;
}a[N];
bool cmp1(Num x,Num y)
{
	return x.num==y.num?x.id>y.id:x.num<y.num;
}
bool cmp2(Num x,Num y)
{
	return x.num==y.num?x.id<y.id:x.num<y.num;
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>x>>y;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].num;
		a[i].id=i;
	}
	if(x<y)
	{
		sort(a+1,a+1+n,cmp1);
		for(int i=1;i<=y;i++) ans[a[i].id]=2;
		for(int i=y+1;i<=n;i++) ans[a[i].id]=1;
	}
	else if(x==y)
	{
		for(int i=1;i<=x;i++) ans[i]=1;
		for(int i=x+1;i<=n;i++) ans[i]=2;
	}
	else
	{
		sort(a+1,a+1+n,cmp2);
		for(int i=1;i<=x;i++) ans[a[i].id]=1;
		for(int i=x+1;i<=n;i++) ans[a[i].id]=2;
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	return 0;
}