当前位置: 首页 > news >正文

网站和网页的不同凡科建站小程序

网站和网页的不同,凡科建站小程序,美国纽约网站建设费用,大学科技园东区 做网站题目链接 CSP-X2024山东小学组T4:刷题 题目描述 比赛之路多艰,做题方得提升。努力刷题的人在比赛中往往能取得很好的成绩,小红就是这样的人。 为了继续提升自己的编程实力,小红整理了一份刷题题单,并选中了题单中的…

题目链接

CSP-X2024山东小学组T4:刷题

题目描述

比赛之路多艰,做题方得提升。努力刷题的人在比赛中往往能取得很好的成绩,小红就是这样的人。
为了继续提升自己的编程实力,小红整理了一份刷题题单,并选中了题单中的 n n n 道编程题,将它们从 1 1 1 n n n 编号,计划用 m m m 天时间按照题目编号顺序做完所有的题目(一道题目只能在同一天完成,不可以使用多天完成同一道题目)。

在小红的计划中,她完成第 i i i 道题目的时间为 a i a_i ai。因为题目有难有易,小红做题时可以找好朋友小明帮忙解题,通过询问小明一道题目的解法,可以省去这个题目的做题时间。当然了,小红做题是为了提升自己,而不是提升小明。因此小红决定一天最多求助小明一次。

本题 m m m 天中,小红做题时间最长一天的总耗时定义为 T T T(小明帮忙做的题目不计入小红的做题总时间)。请你帮小红求出 T T T 的最小值是多少?

输入格式

第一行两个正整数 n n n m m m,分别表示小红要做的题目数和计划用的天数。
第二行 n n n 个正整数,分别表示每个题目解题所用时间 a i a_i ai

输出格式

输出仅一行,表示 m m m 天中耗时最长一天的总耗时 T T T 的最小值。

样例 #1

样例输入 #1

4 2
1 2 3 3

样例输出 #1

3

样例 #2

样例输入 #2

3 4
999 999 999

样例输出 #2

0

提示

30% 的数据, n ≤ 1000 n \leq 1000 n1000
60% 的数据, n ≤ 10 , 000 n \leq 10,000 n10,000
100% 的数据, n ≤ 100 , 000 n \leq 100,000 n100,000 0 ≤ a i ≤ 10 , 000 0 \leq a_i \leq 10,000 0ai10,000 1 ≤ m ≤ 1000 1 \leq m \leq 1000 1m1000

算法思想

根据题目描述,要在 m m m天里按顺序完成 n n n道题,并且每天都可以求助小明帮忙解决一道题,求做题时间最长的一天总耗时 T T T的最小值,显然可以用二分查找来解决。

那么如何判断二分的结果 m i d mid mid是否满足要求呢?这里可以用贪心的思想,在一天中做题时间不超过 m i d mid mid的情况下,尽可能的多做题,不妨设 c n t cnt cnt天能把 n n n道题做完,当 c n t ≤ m cnt\le m cntm时满足要求。

除此之外,对于小明来说,显然要去解决每一天中耗时最长的那道题。

时间复杂度

最坏情况下,在 1 1 1天里把所有题做完,那么最小值 T = n × a i T=n\times a_i T=n×ai,那么时间复杂度为: O ( n × l o g T ) O(n\times logT) O(n×logT)

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100005;
int n, m, a[N];
bool check(LL mid)
{int cnt = 1, maxx = a[1]; //统计每天里耗时最长的题目所用时间LL sum = a[1]; //统计一天里做题的总时间for(int i = 2; i <= n; i ++){maxx = max(maxx, a[i]); //求一天里耗时最长的题目所用时间if(sum + a[i] - maxx <= mid) sum += a[i]; //如果一天的做题时间不超过mid,那么就再做一题else{cnt ++; //需要的天数增加sum = a[i]; maxx = a[i];}}return cnt <= m; //当做完n道题的天数不超过时,满足要求
}
int main()
{cin >> n >> m;for(int i = 1; i <= n; i ++) cin >> a[i];LL L = 0, R = 1e10; //最坏情况在1天把n道题做完,因此R=n*a[i]while(L < R){LL mid = (L + R) / 2;if(check(mid)) R = mid;else L = mid + 1;}cout << L << endl;
}
http://www.mnyf.cn/news/47425.html

相关文章:

  • 泰安网站建设怎么样东莞搜索排名提升
  • 网站用开源cms济南做网站推广哪家好
  • discuz 做的网站企业网站seo方案案例
  • 做语文题的网站seo的工作流程
  • 做私服网站租给发布站策划方案模板
  • 网线制作原理绍兴seo网站优化
  • 山东菏泽网站建设成都网站seo公司
  • php企业网站模板免费下载百度竞价价格
  • 做网站ps注意事项北京网络排名优化
  • 做网站宁波有什么的网络公司一元手游平台app
  • 武汉做网站公司搜索网站
  • 网站页面设计制作费青岛seo招聘
  • 阿拉善盟网站制作网站怎么快速被百度收录
  • 无锡网站的优化济南seo外包服务
  • 网站建设程序都有哪些上海aso苹果关键词优化
  • 沈阳正规网站建设哪家便宜安卓优化神器
  • 辽宁建设信息网站百度上怎么注册店铺地址
  • 好的企业网站建设免费获客平台
  • 成人网站源码整站打包武汉谷歌seo
  • 建设银行广西分行招聘网站免费网站流量
  • 宿迁网站建设上海推广外包
  • 网页设计基础课程教学目标北京seo网站优化培训
  • wordpress主题 古典武汉本地seo
  • 手机移动开发网站建设友情链接代码模板
  • 怎么给网站做防护willfast优化工具下载
  • python做网站视频杭州网站排名提升
  • 天津手机网站制作百度竞价多少钱一个点击
  • 域名解析后如何建设网站什么叫优化
  • 外贸人才网官网百度小程序关键词优化
  • wordpress扁平主题百度seo快速排名优化