M04135: 月度开销

binary search, http://cs101.openjudge.cn/pctbook/M04135/

思路：该题与上题本质上完全一致，均为假设答案然后二分查找，用时约10分钟（一遍ac)

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

class Solution 
{
    private:
        int N, M;
        vector<int> cost = {};
        int right = 0;
        int left = -1;
    public:
        void get()//输入数据，并设置二分查找的初始条件
        {
            cin >> N >> M;
            int x;
            for (int i = 0; i < N; i++)
            {
                cin >> x;
                right += x;
                if(i==0)
                {
                    left = x;
                }
                else
                {
                    if(x > left)
                    {
                        left = x;
                    }
                }
                cost.push_back(x);
            }
        }
        void solve()
        {
            int ans = 0;
           
            while (left <= right)
            {
                int mid = (right + left) / 2;
                int sum = 0;
                int num = 0;
                for (int x : cost)
                {
                    sum += x;
                    if (sum > mid)
                    {
                        num++;
                        sum = x;
                    }
                }
                num++;
                if (num > M)
                {
                    left = mid + 1;
                }
                else
                {
                    ans = mid;
                    right = mid - 1;
                }
            }
            cout << ans << endl;
        }
};


int main()
{
    Solution s;
    s.get();
    s.solve();
    return 0;
}

思路：二分答案

#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
int a[100002];
int main() {
    cin >> n >> m;
    int l = 1, r = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        r += a[i];
        l = max(l, a[i]);
    }
    while (l <= r) {
        int mid = l + (r - l) / 2;
        int fajo = 0, tmp = 1;
        for (int i = 0; i < n; i ++) {
            if (fajo + a[i] > mid) {
                fajo = a[i];
                tmp ++;
            } else fajo += a[i];
        }
        if (tmp <= m) r = mid - 1;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}