思路
设Xi i时刻选多少人加入工作,num[i] 为总共竞选的人数
1)0 <= Xi <= num[i];
2) Xi-7 + Xi-6 + .. + Xi >= r[i];
结论二提示我们用前缀和去做。
设 Si 为前i个时刻选了多少人,整理1, 2 得到
1)0 <= Si - Si-1 <= num[i] => S[i] >= Si-1 + 0, Si-1 >= Si - num[i] (1 <= i <= 24)
2) 分两种情况 i >=8 时 Si - Si-8 >= r[i] => Si >= Si-8 + r[i];
i < 8 时候 i Si + S24 - Si+16 >= r[i] => Si >= Si+16 - S24 + r[i];
由于答案就是S24取最小,那么只要从小到大枚举S24取值找到第一个解就是答案。
注意由于每次要把S24当成一个不变的量假设c 因此需要满足 S24 >= c && S24 <= c
由于找转化成边来维护,S0 = 0 所以 S24 >= c + S0 , S0 >= S24 - c;满足上述约束的不等式即可求解。