【題解】LuoGu6398：KOLEKCIJA

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

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

• 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 ) a_i-a_{j+1}+1>=k:dp_i=dp_j+(a_i-a_{j+1}+1)=(dp_j-a_{j+1})+(a_i+1) ai??aj+1?+1>=k:dpi?=dpj?+(ai??aj+1?+1)=(dpj??aj+1?)+(ai?+1)
  在滿足條件的情況下，用一個變數 s s s記錄 d p i ? a j + 1 dp_i-a_{j+1} dpi??aj+1?的最小值即可，然后 j j j可以用小指標 p p p掃一下，任何時候 p p p滿足 a i ? a p + 1 + 1 > = k a_i-a_{p+1}+1>=k ai??ap+1?+1>=k
• a i ? a j + 1 + 1 < k : d p i = d p j + k : a_i-a_{j+1}+1<k:dp_i=dp_j+k: ai??aj+1?+1<k:dpi?=dpj?+k:這邊又可以發現 d p dp dp陣列值其實是不降的，那么要想求出條件范圍內最小的 d p j dp_j dpj?，只要讓 j j j最小，然后這個最小的 j j j其實就是 p + 1 p+1 p+1

然后就優化到 O ( n ) O(n) 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;
}