NOI 4135:月度开销

题目

http://bailian.openjudge.cn/practice/4135/

思路

开始使用的 dp,但是后来发现 Memory 超了,一看确实 m,n 最大到10w,开个二维数组肯定超了
这题使用二分搜索,使用 isTrue 检验是否合法,合法就将右边界变成mid,否则 left = mid+1

源码

//
//  4135.cpp
//  test
//
//  Created by bytedance on 2020/9/9.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;


vector<int> cost;
int m,n;
bool isTrue(int target){
    int sum = 0;
    int cnt = 1;
    for(int i = 0;i < cost.size();++i){
        if(cost[i] > target)return false;
        if(sum+cost[i]>target){
            sum=cost[i];cnt++;
        }else{
            sum+=cost[i];
        }
        if(cnt>m)return false;
    }
    return true;
}
int main(){

    cin >> n >>m;
    int left=0,right=0,mid;
    int t = n;
    while(t--){
        int a;
        cin >> a;
        left = max(left,a);
        right += a;
        cost.push_back(a);
    }
    while(left<right){
        mid = left+(right-left)/2;
       // cout << left<<" "<<right<<endl;
        if(isTrue(mid)){
           // cout << mid<<" t"<<endl;
            right = mid;
        }else{
            left = mid + 1;
            //cout << mid<<" f"<<endl;
        }
    }
  //  cout << isTrue(1900);
    cout<<left;

    return 0;
}

发布于 :NOI

发表评论

电子邮件地址不会被公开。 必填项已用*标注