数列分段 II

题目描述

思路

代码

#include <cstdio>

int n, m, arr[100005], ans;

int l, r, mid, inf = 0x7f3f3f3f;

inline int read() {

	int s = 0, f = 1;

	char ch = getchar();

	while (ch < '0' || ch > '9') {

		if (ch == '-') f = -1;

		ch = getchar();

	}

	while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();

	return s * f;

	return 0;

}

bool valid(int x) {

	int cnt = 0, sum = 0;

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

		if (arr[i] > x) return false;

		if (sum + arr[i] <= x) sum += arr[i];

		else cnt++, sum = arr[i];

	}

	if (sum != 0) cnt++;

	return cnt <= m;

}

int main() {

	n = read(), m = read();

	for (int i = 1; i <= n; ++i) arr[i] = read();

	l = 0, r = inf;

	while (l <= r) {

		mid = l + r >> 1;

		if (valid(mid)) ans = mid, r = mid - 1;

		else l = mid + 1;

	}

	printf("%d", ans);

	return 0;

}

巴特西

数列分段 II

题目描述

思路

代码

最新文章

热门文章