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

本文主要是介绍【百题详解】洛谷P8508 做不完的作业，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

洛谷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 10 4 10
9 1

输出 #2

输入 #3

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

输出 #3

说明/提示

样例 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;
}

是不是觉得很简单？