首页 > 其他分享 >月度开销--二分法

月度开销--二分法

时间:2023-08-09 20:31:55浏览次数:36  
标签:开销 -- sum 二分法 int fajo include maxf

【题目描述】 农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 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。其他任何分配方案都会比这个值更大。

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int a[100005];
int main()
{
	int n,m;
	cin>>n>>m;
	int sum=0;
	int maxf=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		maxf=max(maxf,a[i]);
		sum+=a[i];
	}
	
	int l=maxf,r=sum;
	while(l<=r)
	{
		int mid=(l+r)/2;
		int t=0,cnt=1;
		for(int i=1;i<=n;i++)
		{
			t+=a[i];
			if(t>mid)
			{
				t=a[i];
				cnt++;
			}
		}
		if(cnt>m)
		{
			l=mid+1;
		}else
		{
			r=mid-1;
		}
	}
	cout<<l<<endl;
	return 0;
}

标签:开销,--,sum,二分法,int,fajo,include,maxf
From: https://blog.51cto.com/u_16200950/7025095

相关文章

  • Spring Boot 链路追踪 SkyWalking 入门
    1.添加SkyWalking依赖:打开您的SpringBoot项目的pom.xml文件,并在<dependencies>标签中添加以下依赖:xml<dependency><groupId>org.apache.skywalking</groupId><artifactId>apm-toolkit-trace</artifactId><version>8.0.0</ver......
  • 瑞熙贝通高校智慧实验室建设项目管理全面升级信息化助力提高效率
    一、系统概述实验室的建设与发展规划,要纳入学校及事业总体发展规划,要考虑环境、设施、仪器设备、人员结构、经费投入等综合配套因素,按照立项、论证、实施、监督、竣工、验收、效益考核等“项目管理”办法的程序,由学校或上级主管部门统一归口,全面规划。但现实建设和管理过程中,仍然存......
  • LRU机制:哈希表+双向链表 [labuladong-刷题打卡 day9]
    今天的知识点LRU缓存机制的实现。学过计组都知道LRU算法(leastrecentlyused最近最少使用算法)是资源管理中的常用算法。那么他是如何实现的呢?LRU原理和Redis实现146.LRU缓存此题算是对LRU机制的一个简化。为了使查找删除在O(1)中实现,我们结合哈希表和双向链表各自在查找和......
  • 文件操作
    一、一切皆文件Linux/UNIX操作系统把所有的服务、设备、协议都抽象成文件的形式,提供了一套统一而简单的文件IO的系统调用,简称系统的文件IO也就是说在UNIX\Linux中任何对象都可以被当做是某种特殊的文件,都可以像访问文件一样,访问这些对象文件分类:普通文件-包括纯文......
  • Oracle 安装 Failed to Create oracle Oracle Home User 解决方案
    WindowsServer2016安装Oracle12报错:FailedtoCreateoracleOracleHomeUser的解决方案:1、打开域安全策略(secpol.msc)-安全设置-账户策略-密码策略-密码必须符合复杂性要求。定义这个策略设置为:已禁用。 2、最后cmd运行刷新组策略命令为:gpupdate/force 3、重新......
  • 8.09日
    我们的人生充满了回忆,它们是我们过去经历的一部分,也是我们成长的见证。回忆可以是美好的,也可以是痛苦的,它们可以让我们笑,也可以让我们哭。回忆是如此珍贵,它们承载着我们的情感和记忆,让我们能够重新体验过去的时光。回忆是一种神奇的力量,它们可以将我们带回到过去,让我们重新感受那......
  • CF578E Walking! 反思--zhengjun
    WA了十几发,清醒了之后发现自己是个sb。首先肯定贪心选,让每条链尽量长即可。最后直接跑个欧拉回路即可(两个点的欧拉回路(ˉ▽ˉ;)...)。分析一下,发现两个点的度数一定满足要求,无非就是是否联通。那么如果两个点之间没有连边并且两个点都有自环,那么就会不连通。只需要考虑这种......
  • 开放式字幕——声画同步效果
    把窗口调到字母和图形也可以窗口-文本在下面调整字母时间想改样式就在基本图形里面......
  • oFono/dbus-python环境搭建以及简单认识
    关键词:D-Bus、oFono、dbus-python、ofonod等等。1.oFono环境搭建(Buildroot+QEMU)和启动1.1Buildroot配置ofonod+dbus-python配置oFono:Targetpackages->Networkingapplication->connman->enableofonosupport使能Python3:Targetpackages->Interpreterlanguage......
  • 设置Oracle视图查询权限的步骤(oracle视图查询权限)
    设置Oracle视图查询权限的步骤是向用户授予SELECT对设定视图的权限。Oracle提供了两种主要方式来授予用户查询视图的权限,分别是直接授权和使用角色授权。本文将介绍如何正确地设置授权,使用Oracle视图。 首先,要设置Oracle视图查询权限,必须具有包括CREATEVIEW权限和SELECT权限的......