Codeforces1631D. Range and Partition

传送门

题目大意

给定一个长为 \(n(1\leq n\leq 2\times 10^5)\) 的序列 \(a(1\leq a_i\leq n)\)， 要将其划分为 \(k(1\leq k\leq n)\) 个子段，每个字段需要满足字段中在 \([x,y]\) 内的数字数量大于不在的数量，求出 \(y-x\) 最小的 \([x,y]\) 以及划分方式。

思路

考虑到对于一个区间，如果能够划分处 \(>k\) 个合法的字段，我们只要合并一些字段，显然其仍然合法，就可以得到正好 \(k\) 个字段，我们可以从前往后考虑，记在第 \(i\) 个字段在区间内的数字数量为 \(in_i\) ，不在的为 \(out_i\) ，于是对于前 \(k-1\) 个字段有 \(in_i=out_i+1\) ，对于最后一个字段有 \(in_k\geq out_k+1\) ，于是可以得到能够划分出 \(k\) 个满足要求的字段的条件为 \(\sum_{i=1}^{k}in_i\geq\sum_{i=1}^{k}out_i+k\) ，也就是整个序列中，在区间内的数字总数 \(\geq \lfloor\frac{n+k+1}{2}\rfloor\) 。我们可以求出序列中每个数字的个数并求其前缀和 \(s\) ，于是问题相当于找出一个最小的区间 \([x,y]\) ，使得 \(s_y-s_{x-1}\geq \lfloor\frac{n+k+1}{2}\rfloor\) ，可以用双指针在 \(O(n)\) 内解决，最后从前向后推出字段的划分方式即可。

代码

#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
#define all(x) x.begin(),x.end()
//#define int LL
//#define lc p*2+1
//#define rc p*2+2
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const LL MOD = 100000000;
const LL mod = 998244353;
const int maxn = 200010;

int T, N, K, A[maxn], cnt[maxn], S[maxn];

void solve()
{
	int need = (N + K + 1) / 2;
	int ans = inf, ax = 0, ay = 0;
	int l = 1, r = 1;
	while (l <= N)
	{
		while (r <= N && S[r] - S[l - 1] < need)
			r++;
		if (r == N + 1)
			break;
		if (r - l < ans)
			ans = r - l, ax = l, ay = r;
		l++;
	}
	cout << ax << ' ' << ay << endl;
	if (K == 1)
	{
		cout << 1 << ' ' << N << endl;
		return;
	}
	int cnt = 0, in = 0, out = 0;
	for (int i = 1; i <= N; i++)
	{
		for (int j = i; j <= N; j++)
		{
			if (A[j] >= ax && A[j] <= ay)
				in++;
			else
				out++;
			if (in > out)
			{
				in = out = 0;
				cnt++;
				cout << i << ' ' << j << endl;
				if (cnt == K - 1)
				{
					cout << j + 1 << ' ' << N << endl;
					return;
				}
				i = j;
				break;
			}
		}
	}
}

int main()
{
	IOS;
	cin >> T;
	while (T--)
	{
		cin >> N >> K;
		for (int i = 1; i <= N; i++)
			cnt[i] = S[i] = 0;
		for (int i = 1; i <= N; i++)
		{
			cin >> A[i];
			cnt[A[i]]++;
		}
		for (int i = 1; i <= N; i++)
			S[i] = S[i - 1] + cnt[i];
		solve();
	}
	return 0;
}