题解 P6398 【[COI2008] KOLEKCIJA】

ModestCoder_ · 2020-10-25 20:24:17 · 题解

先升序排序

令dp_i表示包含这一个的答案

然后，求方案

如果dp_i-dp_{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:dp_i=dp_j+(a_i-a_{j+1}+1)=(dp_j-a_{j+1})+(a_i+1)

在满足条件的情况下，用一个变量s记录dp_i-a_{j+1}的最小值即可，然后j可以用小指针p扫一下，任何时候p满足a_i-a_{p+1}+1>=k

• a_i-a_{j+1}+1<k:dp_i=dp_j+k:$这边又可以发现$dp$数组值其实是不降的，那么要想求出条件范围内最小的$dp_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;
}