Codeforces ~ 1009C ~ Annoying Present (贪心)

2024-09-06 03:58:13

题意

一个长度为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=;

    scanf("%I64d%I64d",&n,&m);

    ll MAX,MIN;

    MAX=n*(n-)/;

    MIN=(n/+)*(n/) - (n%?:n/);

    while(m--)

    {

        scanf("%I64d%I64d",&x,&d);

        sum+=x*n;

        if(d>)

        sum+=MAX*d;

        if(d<)

        sum+=MIN*d;

    }

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

}

最新文章

热门文章