洛谷 P1182 数列分段 Section II

洛谷传送门

题目描述

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

关于最大值最小：

例如一数列4 2 4 5 142451要分成33段

将其如下分段：

[4 2][4 5][1][42][45][1]

第一段和为66，第22段和为99，第33段和为11，和最大值为99。

将其如下分段：

[4][2 4][5 1][4][24][51]

第一段和为44，第22段和为66，第33段和为66，和最大值为66。

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

所以可以得到要将数列4 2 4 5 142451要分成33段，每段和的最大值最小为66。

输入格式

第11行包含两个正整数N，M。

第22行包含NN个空格隔开的非负整数A_iA**i，含义如题目所述。

输出格式

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

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

对于20%20%的数据，有N≤10N≤10；

对于40%40%的数据，有N≤1000N≤1000；

对于100%100%的数据，有N≤100000,M≤N, A_iN≤100000,M≤N,A**i之和不超过10^9109。

题解：

这题其实说的就是数学化了一点，其实实现的时候和P2882和JDOJ 2225是一样的，（就是原题原代码），我JDOJ 2225讲解的详细一点，所以就用JDOJ 2225的题解来看吧。

题解

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=1e5+10;

int n,m,cnt,tot;

int l,r,ll,rr;

int a[maxn];

bool check(int x)

{

    tot=0;cnt=0;

    for(int i=1;i<=n;i++)

    {

        if(tot+a[i]<=x)

        {

            tot+=a[i];

            continue;

        }

        tot=a[i];

        cnt++;

    }

    if(tot>0)

        cnt++;

    if(cnt<=m)

        return 1;

    else

        return 0;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&a[i]);

        ll=max(ll,a[i]);

        rr+=a[i];

    }

    l=ll;r=rr;

    while(l<r)

    {

        int mid=(l+r)/2;

        if(check(mid))//二分的答案域表示领到工资最多的那一次最小的工资额

            r=mid;

        else

            l=mid+1;

    }

    printf("%d",l);

    return 0;

}

巴特西

洛谷 P1182 数列分段 Section II

洛谷 P1182 数列分段 Section II

题目描述

输入格式

输出格式

输入输出样例

说明/提示

题解：

最新文章

热门文章