I - Monthly Expense POJ - 3273

ZYH学长非常菜，这一天他看到了这一题:

给你一个长度为N的序列，现在需要把他们切割成M个子序列（所以每一份都是连续的），使得每个子序列和均不超过某个值X

但是ZYH学长实在太菜了,这个问题困扰了他很久,你可以帮他敲个代码吗？

输入 多组输入输出
每组数据第一行是2个整数N,M（1<=M<=N<=100000），接着是N行，每行一个整数vj，1<=v[j]<=10000,表示这个序列.

输出 输出X的最小值

输入样例 7 5 100 400 300 100 500 101 400

输出样例 500

思路

二分答案，在一个Judge函数进行检验答案是否正确

代码

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

#define ll long long 
const ll mxn = 200005;
const ll INF = 0x3f3f3f3f;
ll ar[mxn];
ll n,m;

bool Judge(ll mid)
{
    ll cnt = 0;
    ll sum = 0;
    for(ll i = 1; i <= n; i ++)
    {
        sum += ar[i];
        if(sum == mid)
        {
            sum = 0;
            cnt ++;
        }
        else if(sum > mid)
        {
            sum = ar[i];
            cnt ++;
        }
    }

    if(sum)
        cnt ++;
    return cnt > m;	//这里一定 大于不能是大于等于，因为 当 cnt == m时候我们考虑能否让这个二分的答案更小呢，所以要让 jude 函数返回假值，是 r = mid - 1，来减小上限
}

int main()
{
    /* freopen("A.txt","r",stdin); */
    /* freopen("Ans.txt","w",stdout); */
    while(scanf("%lld %lld", &n, &m)!= EOF)
    {
        ll l = 0;
        ll r = 0;
        for(ll i = 1; i <= n; i ++)
        {
            scanf("%lld", &ar[i]); 
            l = max(l, ar[i]);
            r += ar[i];
        }
        ll ans = l; 
        while(l <= r) 
        {
            ll mid = (l + r) >> 1;
            if(Judge(mid))
            {
                l = mid + 1;
            }
            else
            {
                ans = mid;
                r = mid - 1;
            }
        }
        printf("%lld\n", ans);
    }

    return 0;
}

总结：做了，好几遍都没有能懂弄明白好 二分时的调整上下限的条件，自己应该反思一下??

I - Monthly Expense POJ - 3273

原文：https://www.cnblogs.com/lql-nyist/p/12686991.html