[数据结构与算法]Range and Partition （贪心+双指针）

D. Range and Partition

[Link](D. Range and Partition)

题意

给你一个长为$n$的数组，让你分成$k$段，满足每段在$[x,y]$内的严格大于在在$[x,y]$外的，请你最小化$y?x$并输出切割方案。

思路

设$cnt1：在[x,y]内的个数，cnt2：不在[x,y]内的个数，f(l,r)：原数组a[l],a[l+1],...,a[r]中cnt1?cnt2的值$。

$f()$的性质：$1.f(l,r)>0则该区间一定满足条件，2.f(l,r)=(l,mid)+(mid+1,r)满足合并$

若$f(l,r)>0，不妨设f(l,r)==k，$则该区间可分为$k$个满足条件的区间。

证明:

首先设$f(l,r)==k>0$，如有一个位置$x$使得$f(l,x)==1$,那么我们就可以从这个位置切割，使得$f(x+1,r)==k?1$。

又因为$f(l,l?1)==0$，（空区间无意义），且$f(l,r)==k$，$f(l,xx)\to f(l,xx+1)$时值最多边$1$，因此类似于零点存在定理，一定存在某个点$x$满足$f(l,x)==1$。

如果我们知道想要分成$k$段，则要满足$cnt1?cn2==k,cnt1+cnt2==n\to cnt1=?(n+k)/2?$

因此我们可以拿双指针从头到尾扫一下值域判断一下满足条件$cnt1=?(n+k)/2?$的最小区间，然后从头到尾暴力扫，如果当前$f()==1$输出这个区间即可。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <bitset>
#include <unordered_map>
#include <cmath> 
#include <stack>
#include <iomanip>
#include <deque> 
#include <sstream>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 2e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
#define tpyeinput int
inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
	e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N], s[N];
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int T;
	cin >> T;
	while (T -- ) {
		cin >> n >> k;
		for (int i = 1; i <= n; i ++) cin >> a[i], s[a[i]] ++;
		int len = (n + k + 1) / 2, resl = 1, resr = n, mn = n, last = 1;	
		int sum = 0;
		for (int i = 1, j = 1; i <= n; i ++) {			
			while (j <= n && sum < len) sum += s[j ++];
			if (sum < len) break;
			if (j - i < mn) {
				mn = j - i;
				resl = i, resr = j - 1;				
			}
			sum -= s[i];
		}
		
		cout << resl << ' ' << resr << endl;
		sum = 0;
		for (int i = 1; i <= n; i ++) {
			if (a[i] >= resl && a[i] <= resr) sum ++;
			else sum --;
			
			if (sum > 0)  {
				if (k != 1)
					cout << last << ' ' << i << endl;
				else {
					cout << last << ' ' << n << endl;
					break;
				} 
				last = i + 1;
				k --;	
				sum = 0;				
			}
		}
		for (int i = 1; i <= n; i ++) s[i] = 0;
	}
	return 0;
}