题目描述
难度分:$1700$
输入$n(1 \leq n \leq 2 \times 10^5)$,$m(1 \leq m \leq 10^9)$和长为$n$的数组$a(1 \leq a[i] \leq m)$。
硬盘可用空间为$m$。
有$n$个视频,下载第$i$个需要$a[i]$分钟,占用$a[i]$的硬盘空间。
- 同一时间只能下载一个视频,一旦视频开始下载,就会立刻占用$a[i]$的硬盘空间。
- 视频下完才能看。每个视频都恰好花$1$分钟看完,看完后可以立刻删除视频,释放空间。
- 你可以在看视频的同时下载另一个视频(如果硬盘空间足够的话)。
你需要下载并看完这$n$个视频。问:到看完最后一个视频,最少要用多少分钟?
输入样例$1$
5 6
1 2 3 4 5
输出样例$1$
16
输入样例$2$
5 5
1 2 3 4 5
输出样例$2$
17
输入样例$3$
4 3
1 3 2 3
输出样例$3$
12
算法
贪心构造+双指针
很显然下载时间肯定是满打满算的,如果磁盘空间只能存放一个视频,那答案肯定就是$n+\Sigma_{i=1}^{n}a[i]$。否则就可以边看边下载,从而节省时间。
如果存在两个视频$i$和$j$满足$a[i]+a[j] \leq m$,那就可以在下载其中一个的同时观看另外一个,节省$1$的时间(观看一个视频的时间,此时另一个视频也下载了$1$的时间)。所以目的就是尽可能多凑出一些$a[i]+a[j] \leq m$的数对$(i,j)$,并且在这个过程中保证磁盘中最多只有两个视频。先对$a$排序,假设选出来$k$个数对,则可以这样构造$k+1$、$1$、$k$、$2$、……,这样构造可以让相邻两个视频的占用空间之和的最大值最小化。因此可以用相对而行的双指针来进行配对,在原始答案$n+\Sigma_{i=1}^{n}a[i]$的基础上不断减小$1$单位的时间代价得到最终答案。
复杂度分析
时间复杂度
对$a$排序的时间复杂度是$O(nlog_2n)$,双指针算法的时间复杂度是$O(n)$,因此整体的时间复杂度为$O(nlog_2n)$。
空间复杂度
双指针算法只使用了有限几个变量,因此额外空间的瓶颈在于排序,按照快排来算应该为$O(log_2n)$。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 200010;
int n, m, a[N];
int main() {
scanf("%d%d", &n, &m);
LL ans = n;
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
ans += a[i];
}
sort(a + 1, a + n + 1);
int l = 1, r = n;
while(l < r) {
if(a[l] + a[r] <= m) {
++l;
ans -= l < r? 2: 1;
}
--r;
}
printf("%lld\n", ans);
return 0;
}