CF1381C mastermind

首先观察题目,发现题目要求 \(x\) 个一模一样的数

因为这 \(x\) 个数是定下来的,所以从这里突破

假设已经选择了 \(x\) 个数,还剩下 \(n-x\) 个数,我们的目标是从中取出 \(y-x\) 个数,然后让这些数在这 \(n-x\) 个位置里面移动,直到这 \(y-x\) 个数不与原序列上的数一样,然后剩下的 \(n-y\) 个数用这个序列里没有出现的那个数填上即可

首先判断是否有解

我们将剩下的这 \(n-x\) 个数按照个数排序,让出现次数更多的一种数排在后面,如果两种数出现次数相同,则按编号排序

举个例子,样例:

5 2 4
3 1 1 2 5

假设我们选了前两个数作为 \(x\) 个数,那么还剩下

1 2 5

其中 \(1\) 、\(2\) 、\(3\) 的个数都是1(都只出现了一次)

如果我们选择第一个数和第四个数作为 \(x\) 个数,那么还剩下

1 1 5

排序之后变为(分别出现了两次和一次)

5 1 1

换个普遍的,抽象的图

CF1381C mastermind

假设这是已经排好序了的数组,颜色表示不同数字,长方形的长度代表这种数字的出现次数

我们将其按照这种方式进行重排序:

CF1381C mastermind

即将最后一种数字放到最前面,剩下的数字之间的相对顺序不变,然后依次放在后面

注意,现在表示的意义:与原来的长方形相比,所相对的数字的位置该放的数

我知道说了听不懂,所以举个例子

假设原数组

1 2 2 3 3 3

排序后:

3 3 3 1 2 2

代表的意思就是原来放1的位置(第一个位置)现在放3;原来两个放2的位置(第二个位置和第三个位置)现在放了两个三;原来放3的位置(第四五六个位置)现在放了一个1(第四个位置)和两个2(第五六个位置),一 一对应

如果此时最长的一个长方形的长度没有超过总长度的一半,很显然就是一个可行解

如果超过了一半,比如下图

CF1381C mastermind

由于我们还有 \(n-y\) 个位置可以填充,那么就会变成下面这个样子

CF1381C mastermind

如果这 \(n-y\) 个位置让最长的长方形的长度在减小后不在超过总长度的一半,那么此时也是一个解

如果再加上了这 \(n-y\) 个位置之后最长的长方形的长度都还超过了一半,那么就肯定无解了

请认真思考为什么这种放置和重新排序一定是最优的(即不可能存在另一种方式使得在我们这种策略无解的情况下有解)

那么我们只需要限制每个长方形的长度取数即可

有许多细节,建议好好写代码

下面给出参考代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int n;
int a[N];
int pot[N],tot[N],cnt[N],ans[N];
int num;
vector<int> pos[N];
bool vis[N],mark[N];
void init()
{
	num=0;
	for(int i=1;i<=n+1;i++) vis[i]=mark[i]=cnt[i]=tot[i]=pot[i]=0;
	for(int i=1;i<=n+1;i++) pos[i].clear();
}
int read()
{
	int x=0,f=1;char s=getchar();
	while(s<'0'||s>'9')
	{
		if(s=='-') f=-f;
		s=getchar();
	}
	while(s>='0'&&s<='9')
	{
		x=x*10+s-48;
		s=getchar();
	}
	return x*f;
}
bool cmp(int i,int j)
{
	if(tot[a[i]]==tot[a[j]]) return a[i]<a[j];
	return tot[a[i]]<tot[a[j]];
}
int main()
{
	int t=read();
	while(t--)
	{
		n=read();
		int x=read(),y=read();
		for(int i=1;i<=n;i++)
		{
			a[i]=read();
			vis[a[i]]=1;
			pos[a[i]].push_back(i);
			cnt[a[i]]++;
		}
		int temp=n-x;
		for(int i=1;i<=n+1;i++)
		if(vis[i])
		{
			if(temp>min((n+n-y-x>>1),cnt[i]))
			{
				temp-=min((n+n-y-x>>1),cnt[i]);
				tot[i]=min((n+n-y-x>>1),cnt[i]);
			}
			else
			{
				tot[i]=temp;
				temp=0;
				break;
			}
		}
		if(temp)
		{
			printf("NO\n");
			init();
			continue;
		}
		for(int i=1;i<=n+1;i++)
		for(int j=1;j<=tot[i];j++)
		pot[++num]=pos[i][j-1];
		sort(pot+1,pot+num+1,cmp);
		for(int i=num,j=num-tot[a[pot[num]]];j;i--,j--)
		ans[pot[i]]=a[pot[j]],mark[pot[i]]=1;
		for(int j=1;j<=tot[a[pot[num]]];j++)
		ans[pot[j]]=a[pot[num]],mark[pot[j]]=1;
		for(int i=1;i<=n+1;i++)
		if(!vis[i])
		{
			temp=i;
			break;
		}
		if(tot[a[pot[num]]]>n-y)
		for(int i=tot[a[pot[num]]]-n+y+1;i-(tot[a[pot[num]]]-n+y+1)<n-y;i++)
		ans[pot[i]]=temp;
		else 
		for(int i=1;i<=n-y;i++)
		ans[pot[i]]=temp;
		for(int i=1;i<=n;i++)
		if(!mark[i])
		{
			x--;
			ans[i]=a[i];
			mark[i]=1;
			if(!x) break;
		}
		printf("YES\n");
		for(int i=1;i<=n;i++) printf("%d ",ans[i]);
		puts("");
		init();
	}
	return 0;
}
上一篇:佣兵模式


下一篇:费用流