P1182 数列分段 Section II

P1182 数列分段 Section II

题目分析:

  1. 数据大小
  2. 把长度为N的数列分为M段,找出每段和的最大值中的最小值
  3. 二分法:找出答案区间每段和最大值[l,r]
  4. 答案存在一个分界点,[l,x] 为非可取解,x为最优解,[x + 1,r]为可取解
  5. 区间左端点为数列的最大值,右端点为数列的和
  6. 整数二分解题,mid取最小情况(l + r) >> 1;

代码如下:

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;

#define inf 0x3f3f3f3f
#define eps 1e-6
#define db double
#define ll long long
#define  mm(a,x) memset(a,x,sizeof a)
#define pii pair<int,int>
#define pb push_back
#define el endl
#define debug(x) cerr<<#x<<" = "<<x<<endl
#define fgx cerr<<"-------------------------"<<endl
#define shutio ios::sync_with_stdio(false),cin.tie(0)
#define  mk make_pair
#define lowbit(x) (x) & (-x)
#define fi first
#define se second

const int N = 1e5 + 10;

ll n,m;
ll a[N];
ll l,r;

bool check(int x){
    ll tot = 1;
    ll s = 0;
    for(int i = 0; i < n; i ++ ){
        if(s + a[i] > x){
            s = 0;
            tot ++; 
        }
        s += a[i];
    }
    return tot <= m;    
}

int main() {
    shutio;
    cin >> n >> m;
    for(int i = 0; i < n; i ++ ){
        cin >> a[i];
        l = max(l,a[i]);
        r += a[i];        
    }
    while(l < r){
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout<<l;
    return 0;
}
全部评论

相关推荐

05-12 11:09
已编辑
门头沟学院 后端
已注销:没必要放这么多专业技能的描述。这些应该是默认已会的,写这么多行感觉在凑内容。项目这块感觉再包装包装吧,换个名字,虽然大家的项目基本都是网上套壳的,但是你这也太明显了。放一个业务项目,再放一个技术项目。技术项目,例如中间件的一些扩展和尝试。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
点赞 评论 收藏
分享
07-01 17:14
中北大学 Java
兄弟们是真是假
牛客46374834...:我在boss上投java岗从来没成功过
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务