Problem
题目简述
有 \(n\) 个人分别在 \(c_i\) 的时刻来,他们都要在 \(k_1\),\(k_2\) 和 \(k_3\) 窗口干不同的事,当有后面一人也排在在同一窗口时,必须等待前面的人办完事才能轮到他。
问怎么在最优分配情况下,使停留时间最长的人停留时间最短。
思路
这道题的话,涉及到的算法为:贪心。
贪心策略:
设当前时刻来的人为 \(x\),如果发现 \(k_1\),\(k_2\) 和 \(k_3\) 其中有一个窗口空了,就进到空窗口。
否则等待窗口空了之后再进去。
计算最优时间
我们可以算出当前最优时间,与开始时间相减,就可以得到停留时间。
设开始时间为 \(st\),当前最优时间为 \(x\),则停留时间为 \((st - x)\)。
最终的答案为:\(\max((st-x)_1,(st-x)_2\dots(st-x)_n)\)。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10, M = 100010;
ll k[N],t[N],a[N][M];
int main(){
ll n;
for (int i = 1; i <= 3; i++)
scanf("%lld", &k[i]);
for (int i = 1; i <= 3; i++)
scanf("%lld", &t[i]);
scanf("%lld", &n);
ll ans = 0;
for(ll x = 1; x <= n; x++){
ll y,z;
scanf("%lld", &y);
z=y;
for(ll e = 1; e <= 3; e++)
a[e][x % k[e]] = max(a[e][x % k[e]], z) + t[e], z = a[e][x % k[e]];
ans = max(ans, z - y);
}
printf("%lld", ans);
return 0;
}