办事大厅目前有n个人和一个办事窗口,每个人都要在这个窗口办事,第i个人办事所需时间为 t[i]。

时刻0所有人都进入办事大厅,第i个人的不满意度 D[i] 定义为他的事情办完的那个时刻。定义所有人的总不满意度S=Σ[i=1 -> n] Di。

办事处工作人员会合理安排办事顺序,使得总不满意度最小,记为 Smin。

现在,很急的鸡来办事了,鸡可以在任意时刻要求工作人员放下手头的事情,立刻来处理鸡的事情,鸡的事情需要 tc 时间处理完成。假设鸡插队后其余n人的总不满意度最小值变为 Sc,若 Sc-Smin ≤ M,则工作人员将允许鸡的插队,否则工作人员将拒绝。M是工作人员的容忍限度。

现在,请你回答 Q 组询问,即当工作人员的容忍限度为M时,鸡最早能在哪个时刻办完事。

输入描述

第一行输入三个正整数n,Q,tc(1≤n,Q≤10^5, 1≤tc≤10^9),含义如题面所述。

第二行输入n个正整数ti(1≤ti≤10^6),表示第i个人办事所需时间。

接下来Q行,每行一个正整数M(0≤M≤10^18),表示该组询问中工作人员的容忍度。

输出描述

对于每组询问的容忍度,求出鸡在该容忍度下最早能在哪个时刻办完事。

输入样例

4 3 6
4 3 2 1
0
14
1000000000000

输出样例

16
9
6

题目分析

对于总不满度:

$$ S = \sum{i=1}^{n} \sum{j=1}^{i} t_i $$

很明显, 要合理安排办事顺序,使得总不满意度最小, 那么就需要将消耗时间少的任务排在前面。

由于 鸡可以在任意时刻要求工作人员放下手头的事情,那么,有两种情况:

  • 鸡要求插队的时刻,第 i 个人刚好办完。
  • 鸡要求插队的时刻,第 i 个人还没办完。

对于第一种情况, 只需要满足 $ (n - i) * tc <= m $即可, 那么答案应该为 $D[n - m / tc] + tc$ 。

对于第二种情况, 我们可以发现,$ Sc - Smin = (n - i + 1) * tc $ 与 鸡要求插队的时刻在第 i - 1 个人刚好办完相同,并且鸡要求插队的时刻在第 i - 1 个人刚好办完情况下,鸡结束任务的时刻更加靠前。

所以我们可以只考虑 鸡插队的时刻,第 i 个人刚好办完

那么正确答案应该为:$ D[n - m / tc] + tc $

代码实现

#include <iostream>
#include <algorithm>
using namespace std;
using LL = long long;
const int N = 1e5 + 10;

int n, q;
LL m, tt, t[N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q >> tt;
    for(int i = 1; i <= n; ++i) cin >> t[i];
    sort(t + 1, t + n + 1);
    for(int i = 1; i <= n; ++i) t[i] += t[i - 1];
    while(q--) {
        cin >> m;
        int pos = min((LL)n, m / tt);
        cout << t[n - pos] + tt << '\n';
    }
    return 0;
}

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status