MENU

小a与"204" | ACM

May 2, 2019 • 我爱学习

题目大意小a非常喜欢204这个数字
现在他有一个长度为n的序列,其中只含有2,0,4这三种数字
设ai为序列中第i个数,你需要重新排列这个数列,使得
每个数与前一个数差的平方的和最大
注意:我们默认$a_0$=0
输入数据第一行一个整数n
接下来一行n个整数,第i个数表示$a_i$
数据输出输出一个整数,表示每个数与前一个数差的平方的和的最大值
样例输入2
2 4
样例输出20
解释样例1解释:按(4,2)排列是最优的,此时sum=$(4-0)^2$+$(2-4)^2$ = 20
样例输入3
2 0 4
样例输出36
解释样例2解释:按(4,0,2)排列是最优的,此时sum=$(4-0)^2$+$(0-4)^2$+$(2-0)^2$= 36

思路简述

  • 大佬的代码,我觉得思路很神奇
  • 先将数组从小到大排序,(第零位为0)
  • 所以最优的排列是,n , n-n , n-1 , n-(n-1) ,...
#include <bits/stdc++.h>

using namespace std;

int main ()
{
    int n;
    scanf ("%d", &n);

    int nu[100010];
    nu[0]= 0;

    for (int i= 1; i<= n; i++){
        scanf ("%d", &nu[i]);
    }
    sort (nu, nu+n+1);
    long long ans= 0;
    for (int i= n; i> n/2; i--){
        ans+= pow(nu[n-i]- nu[i], 2)+pow(nu[i]- nu[n-i+1], 2);
        //cout<<n-i<<endl;
        //cout<<"   "<<ans<<endl;
    }
    printf ("%lld", ans);
}
Last Modified: September 8, 2021