题目描述

blablabla

样例

自己复习用，非题解，请谅解！

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

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

const int N = 510;
int nums[N], l[N], r[N];
int m, k, sum, t;

bool check(int x)
{
    int s = 0, cnt = 1;
    r[cnt] = m;
    for (int i = m; i > 0; i --)
    {
        if (s + nums[i] <= x) s += nums[i];
        else
        {
            l[cnt ++] = i + 1;
            r[cnt] = i;
            s = nums[i];
        }
    }
    l[cnt] = 1;
    return cnt <= k;
}

int main()
{
    cin >> m >> k;
    for (int i = 1; i <= m; i ++)
    {
        scanf("%d", &nums[i]);
        sum += nums[i];
        t = max(t, nums[i]);
    }
    int ll = t, rr = sum;
    while (ll < rr)
    {
        int mid = ll + rr >> 1;
        if (check(mid)) rr = mid;
        else ll = mid + 1;
    }
check(ll);
for (int i = k; i > 0; i --)
{
    cout << l[i] << ' ' << r[i] << endl;
}


    return 0;    
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla