【題解】LuoGu6398：KOLEKCIJA

原題傳送門
先升序排序
令$d{p}_i$表示包含這一個的答案
$d{p}_i=min(d{p}_j+max(k,a_i-a_{j+1}+1))(j<i)$
然後，求方案
如果$d{p}_i-d{p}_{i-1}=a_i-a_{i-1}$，說明$i$和$i-1$屬於同一個區間
所以可以令$i$屬於的區間右端點為$a_i$，左端點是$a_i-k+1$
否則$i$和$i-1$不屬於同一區間，那就構造$l=a_i,r=a_i+k-1$是最優的
需要判斷的是如果$l<1或r>n$需要區間整體移動一下

但是求$dp$值的部分是$O(m^2)$
需要優化一下
討論

• $a_i-a_{j+1}+1>=k:d{p}_i=d{p}_j+(a_i-a_{j+1}+1)=(d{p}_j-a_{j+1})+(a_i+1)$
  在滿足條件的情況下，用一個變數$s$記錄$d{p}_i-a_{j+1}$的最小值即可，然後$j$可以用小指標$p$掃一下，任何時候$p$滿足$a_i-a_{p+1}+1>=k$
• $a_i-a_{j+1}+1<k:d{p}_i=d{p}_j+k:$這邊又可以發現$dp$陣列值其實是不降的，那麼要想求出條件範圍內最小的$d{p}_j$，只要讓$j$最小，然後這個最小的$j$其實就是$p+1$

然後就優化到$O(n)$了

Code：

#include <bits/stdc++.h>
#define maxn 300010
using namespace std;
struct data{
	int val, id, l, r;
}a[maxn];
int n, m, k, dp[maxn], q[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

bool cmp(data x, data y){ return x.val < y.val; }
bool cmp2(data x, data y){ return x.id < y.id; }

int main(){
	n = read(), k = read();
	m = read();
	for (int i = 1; i <= m; ++i) a[i].val = read(), a[i].id = i;
	sort(a + 1, a + 1 + m, cmp);
	int p = 0, h = 1, t = 0, s = 1e9;
	for (int i = 1; i <= m; ++i){
		dp[i] = 1e9;
		if (a[i].val - a[1].val + 1 <= k){
			dp[i] = k, a[i].l = a[1].val, a[i].r = a[1].val + k - 1;
			continue;
		}
		while (p < i && a[i].val - a[p + 1].val + 1 >= k) s = min(s, dp[p] - a[++p].val);
		dp[i] = min(dp[i], s + a[i].val + 1);
		if (a[i].val - a[p + 1].val + 1 < k && p < i) dp[i] = min(dp[i], dp[p] + k);
		if (dp[i] - dp[i - 1] == a[i].val - a[i - 1].val) 
			a[i].r = a[i].val, a[i].l = a[i].val - k + 1;
			else a[i].l = a[i].val, a[i].r = a[i].l + k - 1;
		if (a[i].l < 1) a[i].r += 1 - a[i].l, a[i].l = 1;
		if (a[i].r > n) a[i].l -= a[i].r - n, a[i].r = n;
	}
	printf("%d\n", dp[m]);
	sort(a + 1, a + 1 + m, cmp2);
	for (int i = 1; i <= m; ++i) printf("%d %d\n", a[i].l, a[i].r);
	return 0;
}