题目
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;
}
个