【Codeforces 1009C】Annoying Present

题意

【题解】

其实就是让你最后这n个数字的和最大。
加上的x没有关系。因为肯定都是加上n个x
所以直接加上就可以了
主要在于如何选取j
显然我们要找到一个位置j.
然后pre[j]+aft[j]的值最大(pre[j]=1+2+3+...+j-1,aft类似
(这是在d大于0的时候,小于0的时候找pre[j]+aft[j]最小的就好)

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 1e5;

int n,m;

ll x[N+10],d[N+10];

ll pre[N+10],aft[N+10];

ll ma,maidx = 1,mi,miidx = 1;

double ans = 0;

int main(){

    ios::sync_with_stdio(0),cin.tie(0);

    cin >> n >> m;

    for (int i = 1;i <= m;i++) cin >> x[i] >> d[i];

    for (int i = 1;i <= n;i++){

        pre[i] = pre[i-1]+i-1;

    }

    for (int i = n;i >= 1;i--){

        aft[i] = aft[i+1] + (n-i);

    }

    ma = pre[1]+aft[1];

    for (int i = 2;i <= n;i++){

        ll temp = pre[i]+aft[i];

        if (temp>ma){

            ma = temp;

            maidx = i;

        }

    }

    mi = pre[1]+aft[1];

    for (int i = 2;i <= n;i++){

        ll temp = pre[i]+aft[i];

        if (temp<mi){

            mi = temp;

            miidx = i;

        }

    }

    for (int i = 1;i <= m;i++){

        ans = ans + n*x[i];

        if (d[i]<0){

            ans = ans + mi*d[i];

        }else{

            ans = ans + ma*d[i];

        }

    }

    ans = 1.0*ans / n;

    cout<<fixed<<setprecision(10)<<ans<<endl;

    return 0;

}

巴特西

【Codeforces 1009C】Annoying Present

最新文章

热门文章