关注
背包容量第一题二分做出来了
public long Solve(int n, int m, int[] weights) {
// write code here
int max = -1;
long sum = 0;
for (int i = 0; i < weights.length; i++) {
if(weights[i]>max){
max = weights[i];
}
sum += weights[i];
}
long start = Math.max(max,sum/m);
long end = sum;
long mid = (start+end)/2;
while(start<end){
mid = (start+end)/2;
if(canHave(m,n,weights,mid)){
end = mid;
}else{
start = mid + 1;mid = mid + 1;
}}
return mid;
}
private boolean canHave(int m,int n,int[] weights,long k){
int leftNum = m-1;long leftWeight = k;
for (int j = 0; j < weights.length; j++) {
if(leftWeight>= weights[j]){
leftWeight -= weights[j];
}else{
leftNum--;leftWeight = k;leftWeight -= weights[j];
}
}
if(leftNum>=0){return true;}
return false;
}
查看原帖
2 评论
相关推荐
查看5道真题和解析 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 26届春招投递记录 #
52400次浏览 427人参与
# 薪资一样,你会选择去大厂还是小公司 #
35136次浏览 130人参与
# 27届实习投递记录 #
148063次浏览 1557人参与
# 哪个瞬间让你对大厂祛魅了? #
645744次浏览 4018人参与
# 实习的内耗时刻 #
242343次浏览 1665人参与
# 求职中的尴尬瞬间 #
42076次浏览 125人参与
# 记录实习开销 #
226676次浏览 1766人参与
# 你找工作的时候用AI吗? #
214750次浏览 1032人参与
# 听劝,这个简历怎么改 #
422970次浏览 1901人参与
# 春招 / 实习投递,你最焦虑的一件事 #
164832次浏览 1814人参与
# 暑假倒计时,你都干了些啥? #
62205次浏览 318人参与
# 机械人还在等华为开奖吗? #
344462次浏览 1658人参与
# 2022届毕业生现状 #
1175288次浏览 7802人参与
# 新凯来求职进展汇总 #
82710次浏览 194人参与
# 职场中那些令人叹为观止的八卦 #
112418次浏览 497人参与
# 华子oc时间线 #
1516431次浏览 7126人参与
# 牛友投递互助,不漏校招机会 #
495204次浏览 5368人参与
# 百度求职进展汇总 #
745730次浏览 6495人参与
# 大厂无回复,继续等待还是奔赴小厂 #
376370次浏览 2119人参与
# 正在实习的你,有转正机会吗? #
528076次浏览 3105人参与
