( ext{Description})
( ext{Solution})
题目有两个重要的条件:
- (yle x)。在能选取的情况下,选取 ( ext{B}) 核心不劣于选取 ( ext{A}) 核心。(其实这句话也不是完全正确)
- ( ext{A}) 核心可以同时处理多个任务。也就是意味着 ( ext{B}) 核心单纯是为了减少最终时间的。
由于最终时间由 ( ext{B}) 核心最终任务的结束时间和 ( ext{A}) 核心最终任务的结束时间决定,还有条件一与二的加持,我们肯定会将最后一个任务给 ( ext{B}) 核心做。
接下来就是如何求得 ( ext{A}) 核心最终任务。根据我们的贪心思想,应该是后面的任务能给 ( ext{B}) 核心就给它。那么从后往前枚举如果两个任务时间差小于当前 (y),第一个任务就必须分给 ( ext{A}) 核心才能保证后面的那个给 ( ext{B}) 核心。
不过这个算法是 (mathcal{O(n imes x)}) 的。
实际上我们发现 ( ext{A}) 核心的最终任务随着 (y) 的减小而前移,所以可以 (mathcal{O(n)}) 做。(看代码会好懂一点)
( ext{Code})
#include<cstdio>
#include<iostream>
using namespace std;
const int N = 1000002;
int n, x, t[N], ans[N], tmp;
int main() {
scanf("%d %d", &n, &x);
tmp = x;
for(int i = 1; i <= n; i ++)
scanf("%d", &t[i]);
for(int i = n; i >= 1; i --) {
if(t[i] - t[i - 1] < tmp) {
while(t[i] - t[i - 1] < tmp && tmp >= 1) {
ans[tmp] = t[i - 1];
tmp --;
}
}
if(tmp == 0)
break;
}
for(int i = 1; i <= x; i ++)
printf("%d
", max(t[n] + i, ans[i] + x));
return 0;
}