牛客小白月赛2 J.美

题目链接

题目描述

最后，Sεlιнα(Selina) 开始了选美大赛。 一如既往地，Sεlιнα 想最大化自己的愉悦度。她品味十分独特，对“美”有自己独到的见解。 她给每位经过层层选拔来到这一关的参赛男友都定义了一个帅气值 RR 。Sεlιнα 需要将这些参赛者排成一排，她对于这个排列的“美”值的定义是：

$\mathrm{B}\mathrm{e}\mathrm{A}\mathrm{u}\mathrm{T}\mathrm{i}\mathrm{F}\mathrm{u}\mathrm{L}={\sum }_{i=1}^n(R_i-R_{i-1})$

其中 $R_i$ 表示排列中第 $i$ 个人的帅气值。特别地，当 $i=1$ 时，有 $R_{i-1}=R_n$。
她依旧想使自己获得最大的愉悦值，所以她要使这个排列的 $\mathrm{B}\mathrm{e}\mathrm{A}\mathrm{u}\mathrm{T}\mathrm{i}\mathrm{F}\mathrm{u}\mathrm{L}$ 值尽可能地大。聪明的你，快来告诉 Sεlιнα，这个最大的值是多少。

输入描述:

第一行一个整数 $N$ ，表示有 $N$ 个男友。
第二行 $N$ 个整数，第 $i$ 个数表示值 $R_i$。

输出描述:

输出共一行，一个整数，表示最大的 $\mathrm{B}\mathrm{e}\mathrm{A}\mathrm{u}\mathrm{T}\mathrm{i}\mathrm{F}\mathrm{u}\mathrm{L}$ 值。

示例1

输入

5
7 3 15 12 8

输出

34

示例2

输入

7
-2 0 8 9 -5 3 10

输出

68

简单排序，不难发现只要一大一小交错排得到的答案一定是最大的，AC代码如下:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll a[N],b[N];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    ll sum=0,id=0;
    for(int i=0;i<n;i++){
        if(i!=n-i-1) b[id++]=a[i],b[id++]=a[n-i-1];
        else b[id++]=a[i];
    }
    for(int i=0;i<n;i++){
        if(i==0) sum+=abs(b[0]-b[n-1]);
        else sum+=abs(b[i]-b[i-1]);
    }
    cout<<sum;
}

最后

以上就是忧虑斑马为你收集整理的牛客小白月赛2 J.美牛客小白月赛2 J.美的全部内容，希望文章能够帮你解决牛客小白月赛2 J.美牛客小白月赛2 J.美所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。