[伯俊]6236小遣い管理

白駿6236小遣い管理

https://www.acmicpc.net/problem/6236

指紋は分かりにくくて、原文を探して直接翻訳します

質問する

http://poj.org/problem?id=3273

Farmer John is an astounding accounting wizard and has realized he might run out of money to run the farm. He has already calculated and recorded the exact amount of money (1 ≤ moneyi ≤ 10,000) that he will need to spend each day over the next N (1 ≤ N ≤ 100,000) days.
FJ wants to create a budget for a sequential set of exactly M (1 ≤ M ≤ N) fiscal periods called "fajomonths". Each of these fajomonths contains a set of 1 or more consecutive days. Every day is contained in exactly one fajomonth.
FJ's goal is to arrange the fajomonths so as to minimize the expenses of the fajomonth with the highest spending and thus determine his monthly spending limit.

ジョンは次のN(1≦N≦100000)日に自分が一日使った通貨(1≦money≦10000)を事前に計算した.

彼は1日または連続した日を含むM(1≦M≦N)個の会計期間を正確に創造したいと思っている.
この会計期間はfajomonthと呼ばれています
すべての日は1つのfajomonthに含まれています

彼はfajomonthを組織して、最も支出の多いfajomonthの支出を最小限に抑えたいと思っています.
この時、この支出の最高価格を印刷します.

に答える

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M;
vector<int> money;

//결정 문제: fajomonths에서의 최대 지출이 x일 때 N개의 날들을 M개의 fajomonths로 구성할 수 있는가?  
bool decision(int x) {
	//구성된 fajomonths의 개수
	int cnt = 1;
	int sum = 0;
	for (int i = 0; i < N; ++i) {
		if (sum + money[i] > x) {
			++cnt;
			sum = money[i];
		}
		else sum += money[i];
	}

	if (cnt <= M) return true;
	return false;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	
	int moneySum = 0;
	int moneyMax = 0;
	for (int i = 0; i < N; ++i) {
		int input;
		cin >> input;
		money.push_back(input);

		moneySum += input;
		moneyMax = max(moneyMax, input);
	}

	double lo = moneyMax;
	double hi = moneySum;
	for (int it = 0; it < 100; ++it) {
		double mid = (hi + lo) / 2;

		if (decision(mid)) hi = mid;
		else lo = mid;
	}

	cout << (int)hi;
	return 0;
}