Poj 3273: Monthly Expense

poj3273.md

Poj 3273: Monthly Expense

題目

分析

最大值最小化 => 二分搜

正負相關性判定

bool C(s) = 可否在分解成 M 個 fajomonths 後，最大的 fajomonth 的值小於等於 s

實作時，改成計算當 fajomonth 的 highest spending = s 時，可分解出幾個 fajomonth, 此值是否 <= M 。至於如何計算，Greedy works.

C(x) 表將會是

0 0 0 1 1 1 1 1

這種形式，而我們的目標是尋找第一個 1 在哪

上下界判定

這題是最小值最大化，使用 (lb, ub]

下界發生在 M = N 時，即每個月都是 fajomonth，此時答案是最大的單月花費 max(money[i])

上界發生在 M = 1 時，只有一個 fajomonth，此時答案是 sum(money[i])

// (lb, ub]
int lb = *max_element(money, money + N) - 1;
int ub = accumulate(money, money + N, 0);

while (ub - lb > 1) {
    int mid = (ub + lb) / 2;
    if (C(mid)) ub = mid;
    else lb = mid;
}

答案為 ub

AC Code

#include <iostream>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

int N, M;
int money[100000];

bool C(int s) {
    for (int i = 0; i < N; i++)
        if (money[i] > s)
            return false;

    int cnt = 0;
    int sum = 0;
    for (int i = 0; i < N; i++) {
        if (sum + money[i] > s) {
            sum = money[i];
            cnt++;
        }
        else {
            sum += money[i];
        }
    }

    cnt++; // 最後一個 fajomonth

    return cnt <= M;
}

int solve() {
    // (lb, ub]
    int lb = *max_element(money, money + N) - 1;
    int ub = accumulate(money, money + N, 0);

    while (ub - lb > 1) {
        int mid = (ub + lb) / 2;
        if (C(mid)) ub = mid;
        else lb = mid;
    }

    return ub;
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++)
        scanf("%d", &money[i]);

    printf("%d\n", solve());

    return 0;
}