题目描述

难度分:$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;
}