Codeforces 1765D. 2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams) D(思维+双指针)
原题链接
中等
作者:
小小_88
,
2023-01-25 19:53:41
,
所有人可见
,
阅读 262
Watch the Videos
C++ 代码
/*
如果下一个看一个的话每个视频需要花 a[i] + 1 的时间。
如果边看边下,则每个视频需要花 a[i] 的时间。
最优的选择方案就是看的同时下一个视频。可以用双指针来模拟。
将所有视频按照大小排序,然后优先看大的视频。
对于右指针 j,判断是否能同时观看左指针 i 指向的视频,如果可以,两个视频不需要多花时间,
就是 a[i] + a[j],令 j 左移,i 右移。如果不行,则只能单独看视频 j,因此时间为 a[j] + 1,
令 j 左移。
通过以上思路已经能用最优的方法观看完所有视频,因为对于每个右指针,左指针指向的视频都是
当前可以观看的最小的视频,如果没法一起看,那么右指针只能单独看。
注意这里需要考虑边界情况,以两个指针相遇作为结束标志,则可能存在 i 和 j 走到同一个位置
的情况,此时 a[i] 还没有被观看,因此需要特判一下将 a[i] 的下载时间加上。
然后最后一个视频必须单独花一分钟看完,所以最终答案需要再 + 1
*/
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
void work()
{
int n, m;
scanf("%d%d", &n, &m);
vector<int> a(n);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
sort(a.begin(), a.end());
int i = 0, j = n - 1;
LL res = 1;
while(i < j)
{
res += a[j];
if(a[i] + a[j] <= m) res += a[i], i++;
else res++;
j--;
}
if(i == j) res += a[j];
printf("%lld\n", res);
}
int main()
{
work();
return 0;
}