CF1552E Colors and Intervals 做题记录

$n \times k$ 个格子，编号从 $1$ 到 $n \times k$，染成 $n$ 种颜色，每种颜色恰好 $k$ 个。
构造 $n$ 个区间，第 $i$ 个区间 $[a_i, b_i]$ 满足

• $1 \le a_i < b_i \le n \times k$
• 第 $a_i$ 个和第 $b_i$ 个格子的颜色都是 $i$。
• 每个格子被包含不超过 $\lceil \frac{n}{k-1} \rceil$ 次。

$1\le n\le 100$，$2\le k\le 100$。

先求出 $pos_{i,j}$ 表示颜色 $i$ 第 $j$ 次出现的位置。

不难发现，只要把 $n$ 个颜色分为 $k-1$ 组，每组大小 $\le \lceil\frac{n}{k-1}\rceil$，不同组的区间互不相交即可。并且每个颜色选择区间 $[pos_{i,j},pos_{i,j+1}]$ 肯定是最优的。

考虑较为简单的情况的构造，$k=2$ 未免太简单了，考虑 $k=3$ 的情况。这时要分 $2$ 组，每组大小 $\lceil\frac{n}{2}\rceil$，稍加思考可以发现，只要按照 $pos_{i,2}$ 排序，前 $\lceil\frac{n}{2}\rceil$ 个颜色选择区间 $[pos_{i,1},pos_{i,2}]$，其它颜色选择区间 $[pos_{i,2},pos_{i,3}]$ 即可。

考虑推广这个构造方法，容易发现，只要重复 $k-1$ 次，第 $T$ 次按照 $pos_{i,T+1}$ 排序，排序后前 $\lceil\frac{n}{k-1}\rceil$ 个颜色选择区间 $[pos_{i,T},pos_{i,T+1}]$ 即可。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int S=105;

int n,k;
int pos[S][S],tot[S];
int ansl[S],ansr[S];
int id[S];

int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n*k;i++)
	{
		int x;
		scanf("%d",&x);
		pos[x][++tot[x]]=i;
	}
	int val=n/(k-1)+!!(n%(k-1));
	for(int i=1;i<=k-1;i++)
	{
		int cnt=0;
		for(int j=1;j<=n;j++) if(ansl[j]==ansr[j]) id[++cnt]=j;
		sort(id+1,id+cnt+1,[&](int x,int y){return pos[x][i+1]<pos[y][i+1];});
		for(int j=1;j<=cnt&&j<=val;j++) ansl[id[j]]=pos[id[j]][i],ansr[id[j]]=pos[id[j]][i+1];
	}
	for(int i=1;i<=n;i++) printf("%d %d\n",ansl[i],ansr[i]);
	return 0;
}