博客

009:月度开销

总时间限制: 1000ms 内存限制: 65536kB

描述


农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。

约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案，他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天，每天被恰好包含在一个fajo月里。

约翰的目标是合理安排每个fajo月包含的天数，使得开销最多的fajo月的开销尽可能少。

输入


第一行包含两个整数N,M，用单个空格隔开。

接下来N行，每行包含一个1到10000之间的整数，按顺序给出接下来N天里每天的开销。

输出


一个整数，即最大月度开销的最小值。

样例输入

7 5
100
400
300
100
500
101
400

样例输出

500

提示


若约翰将前两天作为一个月，第三、四两天作为一个月，最后三天每天作为一个月，则最大月度开销为500。其他任何分配方案都会比这个值更大。

思想：

题目中的“

最大中的最小

”是典型的二分查找的问法，本题中“

最大

”是指money尽可能的大，使得按此money划分的周期数小于或等于M；而“

最小

”就是在前述的money中不断去缩小范围，得到最终结果即可；对于周期数划分可以按照使一个周期的预算最接近给定money，因为划分的cnt在小于M的情况下是可以从已有周期中拿出一些日期来单独成周期且是满足条件的，下面是代码。

#include<iostream>
using namespace std;

int check(int money, int* ar, int N) {
	int cnt = 1, sum = 0;//最后一个sum的1
	for (int i = 0; i < N; ++i) {
		if (sum + ar[i] > money) {
			++cnt;
			sum = 0;
		}
		sum += ar[i];
	}
	return cnt;
}

int solve(int max, int min, int* ar, int M, int N) {
	int l = min, r = max;
	int fajo = max;
	while (l <= r) {
		int mid = l + (r - l) / 2;
		int cnt = check(mid, ar, N);
		/*
		月份等于M时正好分成M个月份;
		小于m时，可以将某些月份中的天数拆开组成新月份，满足分成m个月份
		*/
		if (cnt <= M) {//最大的最小，在最大里面取最小
			r = mid - 1;//money过大，缩小
			fajo = mid;
		}
		else
			l = mid + 1;//money过小，扩大
	}
	return fajo;
}

int main() {
	int N, M;
	cin >> N >> M;
	int* ar = new int[N];
	int max = 0, min = 0;//查找上界（和），查找下界（单日开支中最大的）

	for (int i = 0; i < N; ++i) {
		cin >> ar[i];
		max += ar[i];
		if (ar[i] > min)
			min = ar[i];
	}

	cout << solve(max, min, ar, M, N);

	delete[] ar;
	return 0;
}