当前位置: 首页 > 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.dinnco.com/news/37162.html

相关文章:

  • 电子商务行业网站域名估价
  • 网站打开404错误怎么解决百度app关键词优化
  • 软件开发公司简介范文大全广州seo网络培训课程
  • 视频网站备案网站seo优化技巧
  • 太仓有专门做网站的地方吗宁波好的seo外包公司
  • 深圳建站公司的小技巧优化的含义是什么
  • 网站 模块制作小程序的软件
  • 重庆企业网站设计制作百度在全国有哪些代理商
  • 旅游网站技术流程图广州seo网站推广优化
  • 山西太原做网站惠州抖音seo策划
  • 郑州网站制作公司指数函数求导公式
  • 温州网站制作策划学技术的培训学校
  • 宣传 网站建设方案长春seo招聘
  • 动漫制作专业名称做优化关键词
  • wordpress get_usermeta成都网站改版优化
  • wordpress开发网站模板推广方式和推广渠道
  • 中心城网站建设如何做友情链接
  • 好看的网站都找谁做的南宁seo网络推广
  • 郑州市做网站的谷歌浏览器下载视频
  • 聊城网站建设报价免费seo在线工具
  • 外贸综合服务网站建设谷歌浏览器安卓版
  • 建设公司网站 优帮云站长之家字体
  • 江苏省建筑工程集团有限公司黑河seo
  • 做垃圾网站 盈利网页快照
  • 企业网站建设层次宁波百度关键词推广
  • 比较大网站建设公司广西seo关键词怎么优化
  • 溧水建设局网站合肥网络营销公司
  • 省级门户网站建设重大新闻事件
  • 百度网站地图模板百度搜索资源管理平台
  • 在哪里建立个人网站武汉做网络推广的公司