【2019杭电多校3-D】Distribution of books(二分+DP+线段树)

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=6606

题目大意

给定 (n) 个数,在不改变数的排序状态的情况下,取前 (x) 个数,将这 (x)个数分为 (k) 段,要求每段的和的最大值最小,问这个值是多少。

思路

最大值最小->二分!

然后考虑对二分后的值进行check,在模拟时卡了三个小时没有想出来,然后看了题解,需要在二分后中的check中进行DP操作。

题解给出了一个DP转移式子:(dp[i] = max(dp[j]) + 1) ,其中 (dp[j]) 要求满足:(sum[i] - sum[j] leq x)(sum[i]) 代表第(i)位的前缀和,(x) 为枚举的 (mid) )并且 (i leq j)

(sum[i] - sum[j] leqslant x) 转化 (sum[j] geqslant sum[i] - x)

(sum[i]) 离散化后作为线段树下标进行维护,维护的值为 (dp[i]) 。那么就是在区间 ([val2id(sum[i] - x), m]) 中找到最大的值,其中 (val2id(sum[i] - x)) 是离散化后的 (sum[i] - x) 的值,(m) 为离散化后的数字数目。

AC代码

#include <bits/stdc++.h>

#define llinf 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int MAXN = 2e5 + 5;

namespace Discrete { 
    ll b[MAXN << 2];
    int btol, blen;
    void insert(ll x) { b[btol++] = x; }
    void init() {
        sort(b, b + btol);
        blen = unique(b, b + btol) - b;
    }
    int val2id(ll x) { return lower_bound(b, b + blen, x) - b + 1; }
    ll id2val(int x) { return b[x - 1]; }
}
using Discrete::val2id;
using Discrete::id2val;


class SEG {
public:
    struct node {
        int l, r, maxx;
    } T[MAXN << 2];

    inline void push_up(int rt) {
        T[rt].maxx = max(T[rt << 1].maxx, T[rt << 1 | 1].maxx);
    }

    void build(int rt, int l, int r) {
        T[rt].l = l, T[rt].r = r;
        if (l == r) {
            T[rt].maxx = -inf;
            return;
        }
        int mid = (l + r) >> 1;
        build(rt << 1, l, mid), build(rt << 1 | 1, mid + 1, r);
        push_up(rt);
    }

    void update(int rt, int pos, int v) {
        if (T[rt].l == T[rt].r) {
            T[rt].maxx = v;
            return;
        }
        int mid = (T[rt].l + T[rt].r) >> 1;
        if (pos <= mid) update(rt << 1, pos, v);
        else update(rt << 1 | 1, pos, v);
        push_up(rt);
    }

    int query(int rt, int L, int R) {
        if (L <= T[rt].l && T[rt].r <= R) return T[rt].maxx;
        int mid = (T[rt].l + T[rt].r) >> 1;
        int ans = -inf;
        if (L <= mid) ans = max(ans, query(rt << 1, L, R));
        if (R > mid) ans = max(ans, query(rt << 1 | 1, L, R));
        return ans;
    }

} tree;

int n, k;
int a[MAXN];
ll sum[MAXN];

bool check(ll mid) {
    tree.build(1, 1, Discrete::blen);
    int pos = val2id(0);
    tree.update(1, pos, 0);
    for (int i = 1; i <= n; i++) {
        pos = val2id(sum[i] - mid);
        int tmp = tree.query(1, pos, Discrete::blen);
        tree.update(1, val2id(sum[i]), tmp + 1);
    }
    if (tree.T[1].maxx >= k) return 1;
    else return 0;
}


int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        Discrete::btol = 0;
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        Discrete::insert(0);
        Discrete::insert(-llinf), Discrete::insert(llinf);      // 防止出锅
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i], Discrete::insert(sum[i]);
        Discrete::init();

        ll L = -llinf, R = llinf;   // 二分范围注意!不然会在超大数据挂掉……
        while (L < R) {
            ll mid = (L + R) >> 1;
            if (check(mid)) R = mid;
            else L = mid+1;
        }
        printf("%lld
", L);
    }
}
原文地址:https://www.cnblogs.com/tudouuuuu/p/13888391.html