洛谷P1182 数列分段 Section II
2021/10/1 23:41:11
本文主要是介绍洛谷P1182 数列分段 Section II,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意是给你一个序列,你可以将其分为M段,并且要求分出的每个区间和的最大值最小,问这个最小值是多少。
分析:我们应该想到的是这个问法应该是具有二段性的,那么我们如何去二分呢?事实上我们直接二分答案即可,容易想到如果和越大,那么被分的区间数量就越少,要刚好分为M段,我们只需要看每次分出的段数量是否小于等于M即可,具体代码如下:
#include <iostream> using namespace std; const int N = 100010; int w[N], n, m, l, r; bool check(int mid){ int cnt = 1, s = 0; for(int i=1; i<=n; i++){ // if(w[i]>mid) return false; if(s+w[i]>mid)cnt++, s=0; s+=w[i]; } return cnt<=m;//如果小于等于m,那么答案应该在右边 } int main(void){ cin>>n>>m; for(int i=1; i<=n; i++){ cin>>w[i]; l=max(l, w[i]); r+=w[i]; } while(l<r){ int mid = l+r>>1; if(check(mid))r=mid;//如果小于等于m,那么答案应该在右边 else l=mid+1; } cout<<l<<endl; return 0; }
这篇关于洛谷P1182 数列分段 Section II的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享