Open judge 06月度开销

2023-12-25 16:38
文章标签 open 06 开销 月度 judge

本文主要是介绍Open judge 06月度开销,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

06:月度开销

总时间限制: 1000ms 内存限制: 65536kB
传送门
描述
农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案,他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天,每天被恰好包含在一个fajo月里。约翰的目标是合理安排每个fajo月包含的天数,使得开销最多的fajo月的开销尽可能少。
输入
第一行包含两个整数N,M,用单个空格隔开。
接下来N行,每行包含一个1到10000之间的整数,按顺序给出接下来N天里每天的开销。
输出
一个整数,即最大月度开销的最小值。
样例输入
7 5
100
400
300
100
500
101
400
样例输出
500
提示
若约翰将前两天作为一个月,第三、四两天作为一个月,最后三天每月作为一个月,则最大月度开销为500。其他任何分配方案都会比这个值更大。

/*
二分答案+乱搞.
不难猜想ans在[max1,tot]里, 
然后整体二分区间和. 
同《网线主管》. 
*/
#include<bits/stdc++.h>
#define MAXN 100001
using namespace std;
int tot,n,m,a[MAXN],max1,ans;
bool slove(int x)//乱搞 
{int sum=0,month=1;//开始默认一个月 for(int i=1;i<=n;i++){if(a[i]>x) return 0;if(sum+a[i]>x) sum=a[i],month++;else sum+=a[i];}if(month<=m) return 1;else return 0;
}
int erfen(int l,int r)
{while(l<=r){int mid=(l+r)>>1;if(slove(mid)) ans=mid,r=mid-1;//二分答案. else ans=mid,l=mid+1;}return ans;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)  cin>>a[i],tot+=a[i],max1=max(max1,a[i]);cout<<erfen(max1,tot);return 0;
}

这篇关于Open judge 06月度开销的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/536193

相关文章

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

前端-06-eslint9大变样后,如何生成旧版本的.eslintrc.cjs配置文件

目录 问题解决办法 问题 最近在写一个vue3+ts的项目,看了尚硅谷的视频,到了配置eslintrc.cjs的时候我犯了难,因为eslint从9.0之后重大更新,跟以前完全不一样,但是我还是想用和老师一样的eslintrc.cjs文件,该怎么做呢? 视频链接:尚硅谷Vue项目实战硅谷甄选,vue3项目+TypeScript前端项目一套通关 解决办法 首先 eslint 要

Open a folder or workspace... (File -> Open Folder)

问题:vscode Open with Live Server 时 显示Open a folder or workspace... (File -> Open Folder)报错 解决:不可以单独打开文件1.html ; 需要在文件夹里打开 像这样

android java.io.IOException: open failed: ENOENT (No such file or directory)-api23+权限受权

问题描述 在安卓上,清单明明已经受权了读写文件权限,但偏偏就是创建不了目录和文件 调用mkdirs()总是返回false. <uses-permission android:name="android.permission.WRITE_EXTERNAL_STORAGE"/><uses-permission android:name="android.permission.READ_E

C++入门(06)安装QT并快速测试体验一个简单的C++GUI项目

文章目录 1. 清华镜像源下载2. 安装3. 开始菜单上的 QT 工具4. 打开 Qt Creator5. 简单的 GUI C++ 项目5.1 打开 Qt Creator 并创建新项目5.2 设计界面5.3 添加按钮的点击事件5.4 编译并运行项目 6. 信号和槽(Signals and Slots) 这里用到了C++类与对象的很多概念 1. 清华镜像源下载 https://

Open-Sora代码详细解读(1):解读DiT结构

Diffusion Models专栏文章汇总:入门与实战 前言:目前开源的DiT视频生成模型不是很多,Open-Sora是开发者生态最好的一个,涵盖了DiT、时空DiT、3D VAE、Rectified Flow、因果卷积等Diffusion视频生成的经典知识点。本篇博客从Open-Sora的代码出发,深入解读背后的原理。 目录 DiT相比于Unet的关键改进点 Token化方

F12抓包06-4:导出metersphere脚本

metersphere是一站式的开源持续测试平台,我们可以将浏览器请求导出为HAR文件,导入到metersphere,生成接口测试。 metersphere有2种导入入口(方式),导入结果不同:         1.导入到“接口定义”:自动生成接口API和单接口case(接口自动去重;每个请求生成不同case,重复的请求生成重复的case,名称自动加数字后缀,自动与接口关联)。

error while loading shared libraries: libnuma.so.1: cannot open shared object file:

腾讯云CentOS,安装Mysql时: 1.yum remove libnuma.so.1 2.yum install numactl.x86_64

java基础总结06-面向对象2

1 JAVA类的定义 JAVA里面有class关键字定义一个类,后面加上自定义的类名即可。如这里定义的person类,使用class person定义了一个person类,然后在person这个类的类体里面定义person这个类应该具有的成员变量(即属性)和方法,如这里定义的int id和int age这个两个成员变量,或者叫属性,这个id表示人的身份证号码,人应该具有这个属性,age表示人

【SpringMVC学习06】SpringMVC中实现文件上传

1. 环境准备 springmvc上传文件的功能需要两个jar包的支持,如下 2. 单个文件的上传 2.1 前台页面 简单的写一下前台页面,注意一点的是form表单中别忘了写enctype=”multipart/form-data”属性: <tr><td>商品图片</td><td><c:if test="${itemsCustom.pic !=null}"><img src="/f