一道dp配搜索

# include <bits/stdc++.h>
using namespace std;
long long n, m, h;
long long dp[510][510], a[1010], b[1010];
void dfs(int i, int j) {
	for (int k = 1; k <= i; k++) {
		if (k != 0 && i != 0 && h >= max(b[i] - b[k - 1], dp[k - 1][j - 1])) {
			dfs(k - 1, j - 1);
			cout << k << " " << i << "\n";
			break;
		}
	}
}
int main() {
	cin >> m >> n;
	memset(dp, 0x3f, sizeof(dp));
	for (int i = 1; i <= m; i++) {
		cin >> a[i];
		b[i] = b[i - 1] + a[i];
	}
	dp[0][0] = 0;
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (i < j) {
				dp[i][j] = dp[i][i];
				continue;
			}
			for (int k = j; k <= i; k++) {
				dp[i][j] = min(dp[i][j], max(b[i] - b[k - 1], dp[k - 1][j - 1]));
			}
		}
	}
	h = dp[m][n];
	dfs(m, n);
	return 0;
}

使用二分进行处理，

二分每个人要抄的的页数，

看人数够不够就可以了。

如果人数不够，每个人就多抄几页；

否则每个人就少抄几页。

到最后每个人抄的页数最少，那么时间也最少。

#include <bits/stdc++.h>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int m, k;
int a[N];
int sum;
int cx[N];
int cnt;
int st[N];

bool check(int x) {
    cnt = 0; cx[0] = INF; st[0] = m + 1;
    for (int i = m; i >= 1; i--) {
        if (cx[cnt] + a[i] <= x) {
            cx[cnt] += a[i];
            st[cnt] = i;
        }
        else {
            cnt++;
            cx[cnt] = a[i];
            st[cnt] = i;
        }
    }
    return cnt <= k;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> k;
    for (int i = 1; i <= m; i++) cin >> a[i], sum += a[i];

    int l = 0, r = sum;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    check(l);
    for (int i = cnt; i >= 1; i--) cout << st[i] << ' ' << st[i - 1] - 1 << '\n';
    return 0;
}