程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> SDUT 2778-小明的花費預算（二分答案）

SDUT 2778-小明的花費預算（二分答案）

編輯：C++入門知識

SDUT 2778-小明的花費預算（二分答案）

小明的花費預算

Time Limit: 1000ms Memory limit: 65536K 有疑問？點這裡^_^

題目描述

小明終於找到一份工作了，但是老板是個比較奇怪的人，他並不是按照每月每月的這樣發工資，他覺得你想什麼時候來取都可以，取的是前邊連續幾個月中沒有取的工資，而小明恰好是一個花錢比較大手大腳的人，所以他希望每次取得錢正好夠接下來的n個月的花費。所以讓你把這n個月分成正好m組。每個組至少包含一個月，每組之中的月份必須是連續的，請你為他分組，使得分得的組中最大的總花費最小。

輸入

第一行是兩個整數，n（1 ≤ n ≤ 100,000)和m (1 ≤ m ≤ n) 接下來的n行是連續n個月的花費，第i+1行是第i個月的花費。

輸出

輸出滿足最大的總花費最小的那個組的總花費。

示例輸入

示例輸出

初次接觸二分答案，簡單的說，就是對一個問題的答案，我們可以大致確定一個范圍，然後在這個范圍中二分，為什麼可以二分呢？其實是有要求的，答案要具有單調性。就是說對於mid,經過判斷後，我們可以確定答案一定是在mid左還是mid右。二分答案常用於求極大值中的最小值，極小值中的最大值等。。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
#define maxn 100010
#define pp pair
#define  max(x,y) ( ((x) > (y)) ? (x) : (y) )
#define  min(x,y) ( ((x) > (y)) ? (y) : (x) )
using namespace std;
int n, m, a[maxn], high, low;
bool jduge(int mid)
{
	int cnt = 1, s = 0;

	for (int i = 0; i < n; i++) {
		if (s + a[i] <= mid) {
			s += a[i];
		} else {
			cnt++;
			s = a[i];
		}
	}

	if (cnt <= m) {
		return 1;
	} else {
		return 0;
	}

}
void solve()
{
	int mid;

	while (low <= high) {
		mid = (low + high) / 2;

		if (jduge(mid)) {
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	}

	printf("%d\n", mid);
}
int main()
{
	while (~scanf("%d%d", &n, &m)) {
		high = 0;
		low = 0;

		for (int i = 0; i < n; i++) {
			scanf("%d", a + i);
			low = max(a[i], low);
			high += a[i];
		}

		solve();
	}

	return 0;
}