SDUT 2778 小明的花费预算(二分答案)解题报告

2016-02-18 1,334 次浏览 解题报告

题面

小明的花费预算
Time Limit: 1000ms Memory limit: 65536K

题目描述
小明终于找到一份工作了,但是老板是个比较奇怪的人,他并不是按照每月每月的这样发工资,他觉得你想什么时候来取都可以,取的是前边连续几个月中没有取的工资,而小明恰好是一个花钱比较大手大脚的人,所以他希望每次取得钱正好够接下来的n个月的花费。
所以让你把这n个月分成正好m组。每个组至少包含一个月,每组之中的月份必须是连续的,请你为他分组,使得分得的组中最大的总花费最小。

输入
第一行是两个整数,n(1 ≤ n ≤ 100,000)和m (1 ≤ m ≤ n)
接下来的n行是连续n个月的花费,第i+1行是第i个月的花费。

输出
输出满足最大的总花费最小的那个组的总花费。

示例输入
5 3
3
2
9
4
1

示例输出
9

提示
将5个月分为3组,第一组(3,2),第二组(9),第三组(4,1),第二组的总花费最大为9,若按其他的方式分,花费最大的那一组的总花费将>=9.

来源
lwn

解题思路

这道题的思想是二分答案,即先确定答案的范围,然后在范围内通过不断二分来确定答案。
首先根据题意,我们根据分得的所有组中的最大花费来确定二分的范围 [low, high],最小的情况 low 是花费最大的一个月自成一组,而最大的情况 high 是所有月全部构成一组。确定好二分范围后,每次我们二分时,都取中间值 mid 作为假设的答案,即分得的所有组中的最大花费,然后遍历一遍数组,以 mid 为花费上限尽可能少地分组,并根据分得的组数 cnt 来进行下一步判断:

如果 cnt > m,说明以 mid 作为最大花费分得的组数过多,mid 太小,不是合法答案,故要到右半边继续二分;

如果 cnt <= m,说明以 mid 作为最大花费分得的组数正好或偏少,由于我们是按照花费不大于 mid 且使组数尽可能少的原则分组(不够 m 的话可以通过拆分某些组来使组数达到 m),故 cnt <= m 的情况是合法答案,更新最终结果 ans = min(mid ,ans) 并向左半边继续二分(由于向左二分,每次得到的合法答案都必然比上一次的小,因此我们也可以直接写成 ans = mid)。

这样我们就可以写出本题的代码了:

#include <cstdio>
using namespace std;

int a[100000], n, m;

int Binary(int low, int high);

int main(int argc, char const *argv[]) {
    while(~ scanf("%d %d", &n, &m)) {
        int low = 0, high = 0;
        for(int i=0; i<n; ++i) {
            scanf("%d", &a[i]);
            low = a[i] > low ? a[i] : low;
            high += a[i];
        }
        printf("%d\n", Binary(low, high));
    }
    
    return 0;
}

int Binary(int low, int high) {
    int mid, sum, cnt, ans;
    while(low <= high) {
        mid = (low+high)/2;
        sum = 0;
        cnt = 1;
        //花费不大于 mid 且尽可能少地分组
        for(int i=0; i<n; ++i) {
            if(sum+a[i] <= mid)
                sum += a[i];
            else {
                cnt++;
                sum = a[i];
            }
        }
        if(cnt > m) low = mid+1;
        else { //得到合法答案时更新 ans
            high = mid-1;
            ans = mid;
        }
    }

    return ans;
}

bLue 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2016/02/18/sdut-2778.dream

还不快抢沙发

添加新评论