2019HDU多校第三场 Distribution of books 二分 + DP

题意：给你一个序列，你可以选择序列的一个前缀，把前缀分成k个连续的部分，要求这k个部分的区间和的最大值尽量的小，问这个最小的最大值是多少？

思路：首先看到最大值的最小值，容易想到二分。对于每个二分值mid，我们判断原序列是否可以构成k个区间和小于等于mid的区间，这个可以用DP来做。我们先求出序列的前缀和，这样可以把区间和变成前缀相减的形式。之后，对于当前的前缀和sum[i], 我们找前缀和大于等于sum[i] - mid的状态中dp值最大的向自己转移。如果最后存在状态的dp值大于等于k，那么说明二分的mid值偏大，要缩小上边界。反之亦然。dp用离散化 + 线段树优化，总复杂度O(n * logn) * log(值域）

代码：

#include <bits/stdc++.h>

#define LL long long

#define ls (o << 1)

#define rs (o << 1 | 1)

using namespace std;

const int maxn = 200010;

LL sum[maxn];

LL a[maxn];

LL b[maxn];

int dp[maxn], mx[maxn * 4];

int n, m, tot;

void build(int o, int l, int r) {

	if(l == r) {

		mx[o] = -1;

		return;

	}

	int mid = (l + r) >> 1;

	build(ls, l, mid);

	build(rs, mid + 1, r);

	mx[o] = max(mx[ls], mx[rs]);

}

void update(int o, int l, int r, int p, int val) {

	if(l == r) {

		mx[o] = max(mx[o], val);

		return;

	}

	int mid = (l + r) >> 1;

	if(p <= mid) update(ls, l, mid, p, val);

	else update(rs, mid + 1, r, p, val);

	mx[o] = max(mx[ls], mx[rs]);

}

int query(int o, int l, int r, int ql, int qr) {

	if(ql > qr) return -1;

	if(l >= ql && r <= qr) {

		return mx[o];

	}

	int mid = (l + r) >> 1, ans = -1;

	if(ql <= mid) ans = max(ans, query(ls, l, mid, ql, qr));

	if(qr > mid) ans = max(ans, query(rs, mid + 1, r, ql, qr));

	return ans;

}

bool solve(LL mid) {

	build(1, 1, tot);

	update(1, 1, tot, lower_bound(b + 1, b + 1 + tot, 0) - b, 0);

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

		int p = lower_bound(b + 1, b + 1 + tot, sum[i] - mid) - b;

		int p1 = lower_bound(b + 1, b + 1 + tot, sum[i]) - b;

		int tmp =  query(1, 1, tot, p, tot);

		if(tmp == -1) dp[i] = -1;

		else dp[i] = tmp + 1;

		if(dp[i] >= m) return 0;

		update(1, 1, tot, p1, dp[i]);

	}

	return 1;

}

int main() {

	int T;

//	freopen("input.txt", "r", stdin);

//	freopen("1.in", "r", stdin);

	scanf("%d", &T);

	while(T--) {

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

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

			scanf("%lld", &a[i]);

			sum[i] = sum[i - 1] + a[i];

			b[i] = sum[i];

		}

		b[n + 1] = 0;

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

		tot = unique(b + 1, b + 1 + n + 1) - (b + 1);

		LL l = -2e14, r = 2e14;

		while(l < r) {

			LL mid = (l + r) >> 1;

			if(solve(mid)) l = mid + 1;

			else r = mid;

		}

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

	}

}

巴特西

2019HDU多校第三场 Distribution of books 二分 + DP

最新文章

热门文章