【百题详解】洛谷P8508 做不完的作业

发布时间:2024年01月14日

洛谷P8508 做不完的作业

链接——www.luogu.com.cn/problem/P8508

题目背景

高中的任务是非常艰巨的,要学习十门功课(浙江要学技术)。导致作业超级加倍,这一点在暑假就已经体现出来了。

作业的总量是一定的,但不同作业下发的时间是不一定的,导致每天都要花不同的时间应付作业。此时,如何保证睡眠是一个需要仔细考虑的问题。

题目描述

提示:如果你对题目内容有疑问,可以配合样例更好地阅读。

有?n?个任务,第i?个任务需要 ti??的时间。Eric 要在若干天内依次完成这些任务。Eric 是一个专注的人,所以完成每个任务的时间必须连续

一天有?x?的时间。由于 Eric 需要睡觉,所以 Eric 不能利用所有的时间。具体地:

  • Eric 每天必须睡觉

  • Eric 每天的睡觉的时间是连续的,且睡觉时间结束后,第二天恰好开始;

  • Eric?前?i?天的睡觉时间总和不能少于r?x?i?的时间。r?是一个给定的实数i?是一个正整数。

Eric 想问你,至少需要多少天才能完成任务。

输入格式

第一行输入四个整数n,x,p,q,代表r=qp?。

接下来一行,输入n个整数,第i?个代表ti?。

输出格式

输出一个正整数,代表最小天数。可以证明,在下文限定的数据下,一定存在至少一个解。

输入 #1

3 5 1 3
1 2 2

输出 #1

2

输入 #2

2 10 4 10
9 1

输出 #2

3

输入 #3

10 2 1 2
1 1 1 1 1 1 1 1 1 1

输出 #3

10

说明/提示

样例 1 解释

下面是一种可能的方案:

Eric 先在第一天做任务 1,总共消耗?1的时间,用?4时间睡觉,满足至少要 5×31?=35????的时间睡觉的要求。

Eric 再在第二天加班加点,完成剩下的任务,有?11?的时间睡觉。两天睡觉总量为5≥10×31?=310?,也是满足要求的。

样例 2 解释

Eric 试图在第一天完成任务 1,但假如要做就会熬夜,觉就不够睡。所以 Eric 第一天只能睡大觉。Eric 在第二天完成任务 1 就没有问题。

同时请注意,即使睡觉时间满足了要求,Eric 也不能在第二天就完成任务 2,因为 Eric 必须睡觉。所以 Eric 先睡到第三天,然后完成任务 2。可以证明不存在方案小于三天。

同时注意数据不保证?gcd(p,q)=1。

样例 3 解释

显然一天只能干一件活,所以要?10天。

为了减少评测量,本题开启子任务依赖。具体地,当且仅当前四个子任务全部通过时,子任务 5 才计分,否则子任务 5 计?0分。

解题思路

这题CSDN里没有题解/正确解法,我就来弥补一下吧!

Subtask 1~4

考虑贪心。

证明:假设已求出前i?1?个任务的答案,若再插入一个有更优方案,则在前i?1?个时就应插入,矛盾。

具体实现:枚举天数。对于每一天,判断如果做下一个任务,是否满足题目条件。重复这个过程,可以做的任务则做,否则直接睡大觉。

Subtask 5

优化贪心。

容易发现,如果太多天都在睡大觉,上述做法会炸掉。所以,对于每次无法做任务时,算出接下来需要睡几天大觉,可以做到将近 O(n)。

更神仙的做法

可以发现,前面一直睡大觉,到最后加班加点做任务,是不劣的。所以可以倒序插入任务,再算出前面需要睡几天大觉即可。

70分:

首先考虑最直观地暴力。

枚举每一天,对于第?i?天,先求出今天要睡多少个小时才能满足 r×x×i?的要求。

然后,判断剩下的时间是否够完成某些任务。如果可以完成就完成,不能做就睡觉。

然后发现,这个方法的复杂度至多为 O(nq)。

那么这样暴力可以有多少分呢?

首先对于 subtask 1,保证 n≤3,那么答案显然较小。

对于特殊性质 A,我们可以将式子变为 ti?≤x×(1?qp?)。

这个式子意思就是说,每天至少可以完成一个任务。那么ans≤n,显然也可以跑过。

对于特殊性质 B,保证 nq≤106,也能跑过。

那么就可以拿到 70pts 的好成绩。

那么我们可以考虑优化这个暴力。

首先发现,每次完成某些任务前都会有几天会全部睡觉。

那么我们可以O(1)?求出完成这个任务需要先睡多少天,再完成任务即可。

时间复杂度O(n)。

AC:

#include<bits/stdc++.h>
using namespace std;
long long n,x,p,q,i=1,sum,t,w;
int main(){
	cin>>n>>x>>p>>q;
	while(n--){
		cin>>w;
		if((x-t-w+sum)*q>=i*p*x&&x-t>w){
			t+=w; 
		}
		else{
			sum+=x-t;
			i++;
			long long l=ceil((q*(sum+x-w)-p*i*x)*1.0/(x*p-x*q));
			if(l>0){
				sum+=x*l;//注意:是l不是1!!!
				i+=l;//注意:是l不是1!!!
			}
			t=w;
		}
	}
	cout<<i;
	return 0;
}

是不是觉得很简单??

结尾

如果有人想在洛谷上做题,可以点下方链接:

https://www.luogu.com.cn/

如果你喜欢或想了解一下其他的算法,可以看看以下这些:

DFS深搜:

C++:第十二讲DFS深搜(二)-CSDN博客

C++:第十一讲DFS深搜-CSDN博客

二分:

C++:第十讲二分查找-CSDN博客

前缀和与差分:

C++:第九讲前缀和与差分-CSDN博客

排序:

C++:第七讲冒泡排序-CSDN博客

函数:

C++第6讲max和min函数_c++ min函数-CSDN博客

C++第五讲函数初步-CSDN博客

for循环&数组:

C++第四讲for循环及数组-CSDN博客

if语句&else语句及运算:

C++第三讲:C++中的逻辑运算符及if else语句-CSDN博客

基础:

C++第二讲输入与输出-CSDN博客

C++第一讲认识C++编译器-CSDN博客

欢迎收看,希望大家能三连!

最后认识一下,我是爱编程的喷火龙廖,我们有缘再见!

文章来源:https://blog.csdn.net/2301_81328824/article/details/135572317
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。