LiberOJ 10014 数列分段 II 二分
2022/5/6 6:12:43
本文主要是介绍LiberOJ 10014 数列分段 II 二分,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意
给定长度为 \(N\) 的序列 \(A\),要将其划分为连续的 \(M\) 段,并最小化每一段总和的最大值。
输入格式
第1行包含两个正整数 \(N,M\)
第2行包含 \(N\) 个空格隔开的非负整数 \(A_i\),含义如题目所述。
输出格式
仅包含一个正整数,即每段和最大值最小为多少。
Input
5 3
4 2 4 5 1
Output
6
\(Note:\) 划分方式可以为:\([4,2][4][5,1]\)
Solution
我们二分答案,答案的左端点 \(l = \max_i(A_i)\),右端点 \(r = \sum_i A_i\)
我们每次 \(check\) 答案的时候,统计段落数 \(cnt\).
如果 \(cnt\geq M\),说明我们此时需要增大左端点(因为上限偏小,这样才会使得段落数变多)
\(Code:\)
点击查看代码
int n,m; const int N = 1e5+5; int a[N]; int sum[N]; bool check(int x){ int cnt=0; int cur = 0; for(int i=2;i<=n;i++){ if(sum[i]-sum[cur]>x){ cur = i-1; cnt+=1; } } if(cnt>=m) return true; return false; } int main(){ //ios::sync_with_stdio(false); n = read();m = read(); int l=0,r; for(int i=1;i<=n;i++)a[i] = read(),sum[i] = sum[i-1]+a[i],l = max(l,a[i]); r = sum[n]; int ans = sum[n]; while(l<r){ int mid = (l+r)>>1; if(check(mid)){ l=mid+1; } else{r=mid;} } cout<<r<<endl; }
\(\\\)
这里的二分模板为:
点击查看代码
int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } return l; }
这篇关于LiberOJ 10014 数列分段 II 二分的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性