alt alt

示例1

输入
4 3 6
4 3 2 1
0
14
1000000000000

输出
16
9
6

思路

首先要理解Smin的意思，Smin就是所有人等待时间+自己处理事件的时间的最小值,要达到最小值就要保证处理事务时间少的鸡在前面，处理时间长的鸡在后面，然后抓住Sc-Smin的含义（就是tc*x(n的含义：1+炸鸡插入位置后面的人数)），然后就转化为了x<=M/tc，这时候贪心一下，当取等时，炸鸡能插队插到尽可能的最前面，即转化为求前n-M/tc个人的处理事务的时间和再加上tc，这时我们用一个数组维护一下每个人的处理事务的时间的前缀和即可。

代码

using namespace std;

int n,q;
long long t,m;
int a[100010];
long long b[100010];
int main()
{
    scanf("%d%d%lld",&n,&q,&t);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);//我们希望办事所需要的时间最短的鸡在前面，所以要从小到大排
    for(int i =1;i<=n;i++)
    {
        b[i]=b[i-1]+a[i];
    }
    for(int i =1;i<=q;i++)
    {
        scanf("%lld",&m);
        m=m/t;
        if(n>m)
            printf("%lld\n",b[n-m]+t);
        else
            printf("%lld\n",t);
    }
    return 0;
}