Massive Algorithms: POJ 3273 -- Monthly Expense (最大化最小值)

Description

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 ≤ money_i ≤ 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.

Input

Line 1: Two space-separated integers: N and M
Lines 2..N+1: Line i+1 contains the number of dollars Farmer John spends on the ith day

Output

Line 1: The smallest possible monthly limit Farmer John can afford to live with.

Sample Input

Sample Output

https://amoshyc.github.io/CPsolution/poj/p3273.html

給定長度為 N 的正整數陣列 A[i]，請將他分解成 M 個不重疊區間，則每個區間中有其總和 S[j]，

定義 s = max(S[j] for j in range(M)) （即 S[j] 中的最大值），
請問在所有可能的分解法中，s 最小會是多少？

判斷函式為:

bool C(int d) = 分解成 M 個區間後，最大的區間和 s <= d

該函式有單調性，我們的目標是分隔點的 1 的位置（左邊數來的第一個 1 在哪）:

... 0 0 0 1 1 1 1 ...

明顯地，d 越小越不容易達成。

這個函式可以用 Greedy 實作:

盡量把一個區間的值塞滿，直到塞不下。
也就是說，從左至右迭代 A[i]，如果前一個區間的總和再加上 A[i] 會大於 d 的話，
則 A[i] 就是下個區間的起始點。最後看區間的數量是否 <= M

解的空間 = [max(A[i]), sum(A[i])]

下界發生在 M = N 時，每一項自己都是一個區間，此時 s = max(A[i])；
上界發生在 M = 1 時，每一項都在同一個區間裡，此時 s = sum(A[i])。

C(d) 在解的空間上存在分布全為 1 的情況，即當 C(max(A[i])) = true 情形。
可以預判掉，此時的答案就是 max(A[i])

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++;

    return cnt <= M;
}

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

    if (C(lb)) return lb;

    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;
}

http://blog.sina.com.cn/s/blog_6635898a0100ko8e.html

题意：在接下来的n天里，Farmer John每天需要花money[i]钱，把这些天分成m份（每份都是连续的天），要求每份的和尽量少，输出这个最小的和。

思路：贪心的思想，用二分去做，复杂度为O(nlogM)，M = sum - max。初始状态，上界high为n天花费的总和sum，下界为每天花费的最大值max。然后二分，每次的mid值为（low+high）/ 2，然后根据mid值（估计值）遍历n天花费，看看这个mid值能把n天分成几份，如果份数大于m，表示mid偏小，low = mid + 1，反之high = mid - 1。

int main(){
    int n, m, money[Max];
    scanf("%d%d", &n, &m);
    int i, max = 0, sum = 0;
    for(i = 1; i <= n; i ++){
        scanf("%d", &money[i]);
        if(money[i] > max) max = money[i];
        sum += money[i];
    }

    int mid, low = max, high = sum;
    while(high > low){                    //  二分。
        mid = (high + low) / 2;
        int count = 1, w = 0;
        for(i = 1; i <= n; i ++){         //  count为当前mid值对应的把天分成的份数。
            w += money[i];
            if(w > mid){
                count ++;
                w = money[i];
            }
        }
        if(count > m) low = mid + 1;      //  整数在/2的时候可能造成精度不够，故可+1。
        else high = mid - 1;
    }
    printf("%d\n", high);
    return 0;
}

http://blog.csdn.net/u014688145/article/details/73610408

二分就不用说了，主要是

f(m)函数，给定一个金钱范围，尽可能的塞满，问最多能塞出多少个桶。

static int N; static int M; static int[] money; public static void main(String[] args) throws IOException { Scanner in = new Scanner(System.in); N = in.nextInt(); M = in.nextInt(); money = new int[N]; int max = 0; int sum = 0; for (int i = 0; i < N; ++i){ money[i] = in.nextInt(); max = Math.max(max, money[i]); sum += money[i]; } int lf = max; int rt = sum; while (lf < rt){ int mid = lf + (rt - lf) / 2; if (valid(mid) > M) lf = mid + 1; else rt = mid; } if (valid(lf) <= M) System.out.println(lf); else System.out.println(0); } public static int valid(int m){ int cnt = 0; int sum = 0; for (int i = 0; i < N; ++i){ sum += money[i]; if (sum == m){ sum = 0; cnt++; } else if (sum > m){ sum = money[i]; cnt++; } } if (sum != 0) cnt++; return cnt; }

Read full article from 3273 -- Monthly Expense

POJ 3273 -- Monthly Expense (最大化最小值)

Labels

Popular Posts