2022-05-20每日刷题打卡

代码源——每日一题

分段求和 - 题目 - Daimayuan Online Judge

对于给定的一个长度为 N 的正整数数列 A1−N，现要将其分成 M(M≤N) 段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列 4,2,4,5,1 要分成 3 段。

将其如下分段：[4,2] [4,5] [1]。 第一段和为 6，第 2 段和为 9，第 3 段和为 1，和最大值为 9。

将其如下分段：[4] [2,4] [5,1]。 第一段和为 4，第 2 段和为 6，第 3 段和为 6，和最大值为 6。

并且无论如何分段，最大值不会小于 6。

所以可以得到要将数列 4,2,4,5,1 要分成 3 段，每段和的最大值最小为 6。

输入格式

第 1 行包含两个正整数 N,M。

第 2 行包含 N 个空格隔开的非负整数 Ai，含义如题目所述。

数据范围

1≤N≤10^{5,M≤N,Ai≤10}8
输出格式

一个正整数，即每段和最大值最小为多少。

输入样例

5 3
4 2 4 5 1
1
2

输出样例

6
1

问题解析

二分答案，可以用二分找可能的最大值，左区间为0，右区间为整个数组的和。

每次取一个值作为可能的最大值mid，然后去遍历数组，当计算到的子段和大于mid时，把这个当成一段，然后重新计算下一个子段和，当计算的段数大于k，说明我们枚举的这个mid太小了，我们去右区间找，而且如果有单个元素的值是大于mid的也说明不行（单个元素都大于我们枚举的最大子段和了，那么显然是不行的），如果我们计算段数后小于k的，说明我们的子段和很大，这时候就去左区间找。

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef pair<ll, ll>PII;
const int N = 1e6 + 50;
ll n, k;

bool check(ll ans, vector<ll>& v)
{
    ll sum = 0, cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (v[i] > ans)return false;
        else if (sum + v[i] > ans)
        {
            cnt++;
            if (cnt >= k)return false;
            sum = v[i];
        }
        else sum += v[i];
    }
    return true;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> k;
    vector<ll>v(n);
    ll l = 0, r = 0;
    for (int i = 0; i < n; i++)cin >> v[i], r += v[i];;
    while (l < r)
    {
        ll mid = (l + r) / 2;
        if (check(mid, v))r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60