【zzuliOJ】1919 - 晴天分数字（二分）

FishWang

发布于 2025-08-27 10:53:22

16700

代码可运行

运行总次数：0

代码可运行

点击打开题目

1919: 晴天分数字

Time Limit: 1 Sec Memory Limit: 128 MB Submit: 179 Solved: 38 Submit Status Web Board

Description

晴天想把一个包含n个整数的序列a分成连续的若干段，且和最大的一段的值最小，但他有强迫症，分的段数不能超过m段，然后他就不会分了。。。他想问你这个分出来的和最大的一段的和最小值是多少？

Input

第一行输入一个整数t，代表有t组测试数据。每组数据第一行为两个整数n,m分别代表序列的长度和最多可分的段数。接下来一行包含n个整数表示序列。 0<=n<=50000 1<=m<=n，0<=ai<=10000。

Output

输出一个整数表示和最大的一段的最小值。

Sample Input

13 21 3 5

Sample Output

HINT

1 3 5 分成一段可以为1 3 5和为9，分成两段可以为1，3 5或者1 3，5，和最大的一段值分别为8，5，所以答案为5

Source

haut

题目本来只是个字母，我随便起的。

可以知道结果是个线性的。

代码如下：

#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
int sum[50000+11];
int n,m;
bool check(int x)
{
    if (x >= sum[n])
        return true;
    if (x < sum[1])
        return false;
    int pos = upper_bound(sum+1 , sum+1+n , x) - sum - 1;
    int k = m - 1;
    int ne;
    while (pos != n)
    {
        if (k <= 0)
            return false;
        ne = upper_bound(sum+1 , sum+1+n , sum[pos] + x) - sum - 1;
        if (ne == pos)
            return false;       //x太小
        pos = ne;
        k--; 
    }
    return true;
}
int main()
{
    int u;
    int t;
    int l,r,mid;
    sum[0] = 0;
    scanf ("%d",&u);
    while (u--)
    {
        scanf ("%d %d",&n,&m);
        for (int i = 1 ; i <= n ; i++)
        {
            scanf ("%d",&t);
            sum[i] = t + sum[i-1];
        }
        l = 0;
        r = sum[n];
        while (r >= l)
        {
            mid = (l + r) >> 1;
            if (check(mid))
                r = mid - 1;
            else
                l = mid + 1;
        }
        printf ("%d\n",l);
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

return