Codeforces ~ 1009C ~ Annoying Present (贪心)

题意

一个长度为n的数组（初始全为0），进行m次操作。

操作：给你x，d，你任意挑选一个 i (1~n)，每个数字加上 x+|i-j|*d（ j 表示对应数字的下标）

问m次操作后的最大算术平均值为多少？

 

题解

首先对于x，每次数组的和sum都增加n*x。（Σ|i-j|）*d跟我们选的 i 有关系，如果d>0，我们就让 Σ|i-j| 尽量大，如果d<0，我们就让 Σ|i-j| 尽量小。Σ|i-j|的最大值就是 i 取0或n的时候，Σ|i-j|的最小值就是 i 取n/2的时候。维护sum就行了

#include<stdio.h>
#define ll long long
int main( )
{
    ll n,m,x,d;
    ll sum=0;
    scanf("%I64d%I64d",&n,&m);
    ll MAX,MIN;
    MAX=n*(n-1)/2;
    MIN=(n/2+1)*(n/2) - (n%2?0:n/2);

    while(m--)
    {
        scanf("%I64d%I64d",&x,&d);
        sum+=x*n;
        if(d>0)
        sum+=MAX*d;
        if(d<0)
        sum+=MIN*d;

    }
    printf("%.7f
",1.0*sum/n);
}