题目链接

题意

将一个升序排好的数列切成若干段，要求每段的长度\(\gt k\)，对每一段中最大值与最小值的差取个最大值，问这个最大值最小是多少。

思路

二分答案

怎么check呢？

dp一下。

d[i]表示[1..d[i]]一段可以按上述要求进行切割，且d[i]是i及其之前最靠近i的位置（即从头开始到i位置处最远可以切割到的位置），

则若有d[n]==n，则意味着一整段都可以进行切割。

怎么转移呢？

若[d[i-k]+1,i]一段能被切割，则[1,i]一整段就能被切割，于是有d[i]==i；

否则d[i]继承上次跑到的最远位置last.

Code

#include <bits/stdc++.h>

#define maxn 300010

using namespace std;

int n, k, a[maxn], d[maxn];

bool check(int x) {

    int last = 0;

    for (int i = k; i <= n; ++i) {

        int j = d[i-k];

        if (a[i] - a[j+1] <= x) last = i;

        d[i] = last;

    }

    return d[n] == n;

}

int main() {

    scanf("%d%d", &n, &k);

    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);

    sort(a+1, a+1+n);

    int l = 0, r = a[n] - a[1];

    while (l < r) {

        int mid = l + r >> 1;

        if (check(mid)) r = mid;

        else l = mid+1;

    }

    printf("%d\n", l);

    return 0;

}

巴特西

2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest I. Photo Processing

题目链接

题意

思路

二分答案

怎么check呢？

怎么转移呢？

Code

最新文章

热门文章