C. Annoying Present

题目链接

Educational Codeforces Round 47 (Rated for Div. 2)--C. Annoying Present

题解

简单题。题意大概是给定一个长度为n初始值均为0的数组。对数组做m次操作后求数组算术平均值的最大值。
操作输入x,d,操作为a[j]+x+d*dist(i,j),i为可以选择的某个位置。
分析后发现操作后数组之和的变化与原数组无关,当d大于0时i选择1或n数组之和最大,当d小于0时i选择trunc((1+n)/2)数组之和最大。由此对于每次操作直接用等差数列公式计算即可。

代码

#include <iostream>
#include <algorithm>
using namespace std;

long long n, m;
long long ans, x, d;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> x >> d;
        ans += x * n;
        if (d > 0) {
            ans += d * n * (n - 1) / 2;
        }
        else {
            ans += ((n % 2 == 0) ? (n / 2 * n / 2 * d) : ((n + 1) / 2 * (n - 1) / 2 * d));
        }
    }
    printf("%.20lf",(double)ans / n);
}

标签: math, greedy

添加新评论