小a与“204”------数列、排序

链接：https://ac.nowcoder.com/acm/contest/317/B
来源：牛客网

小a非常喜欢204204这个数字，因为′a′+′k′=204′a′+′k′=204。
现在他有一个长度为nn的序列，其中只含有2,0,42,0,4这三种数字
设aiai为序列中第ii个数，你需要重新排列这个数列，使得∑ni=1(ai−ai−1)2∑i=1n(ai−ai−1)2最大(公式的含义是：每个数与前一个数差的平方的和)
注意：我们默认a0=0a0=0

输入描述:

第一行一个整数nn
接下来一行nn个整数，第ii个数表示aiai

输出描述:

输出一个整数，表示∑ni=1(ai−ai−1)2∑i=1n(ai−ai−1)2的最大值

示例1

输入

2

2 4

输出

20

说明

样例1解释：按(4,2)(4,2)排列是最优的，此时sum=(4−0)2+(2−4)2=20sum=(4−0)2+(2−4)2=20

示例2

输入

3

2 0 4

输出

36

说明

样例2解释：按(4,0,2)(4,0,2)排列是最优的，此时sum=(4−0)2+(0−4)2+(2−0)2=36sum=(4−0)2+(0−4)2+(2−0)2=36

示例3

输入

5

2 4 0 2 4

输出

52

备注:

1⩽n⩽1051⩽n⩽105，保证aiai为2/0/42/0/4中的数

注：依次把第一大和第二大的数存入数组，依次类推，在按公式计算。

#include<iostream>

#include<algorithm>

using namespace std;

bool cmp(int a ,int b)

{

  return a>b;

}

int a[],b[];

int main()

{

  int n,m=;

  scanf("%d",&n);

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

  {

    cin>>a[i];

  }

  sort(a,a+n,cmp);

  int j=;

  b[]=;

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

  {

    if(i%==)

      {

        b[i+]=a[j];

        j++;

      }

    else

      b[i+]=a[n-j];

  }

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

  {

    //cout<<b[i]<<" ";

    m=m+(b[i]-b[i-])*(b[i]-b[i-]);

  }

  printf("%d\n", m);

}

链接：https://ac.nowcoder.com/acm/contest/317/B
来源：牛客网

小a非常喜欢204204这个数字，因为′a′+′k′=204′a′+′k′=204。
现在他有一个长度为nn的序列，其中只含有2,0,42,0,4这三种数字
设aiai为序列中第ii个数，你需要重新排列这个数列，使得∑ni=1(ai−ai−1)2∑i=1n(ai−ai−1)2最大(公式的含义是：每个数与前一个数差的平方的和)
注意：我们默认a0=0a0=0

输入描述:

第一行一个整数nn
接下来一行nn个整数，第ii个数表示aiai

输出描述:

输出一个整数，表示∑ni=1(ai−ai−1)2∑i=1n(ai−ai−1)2的最大值

示例1

输入

2

2 4

输出

20

说明

样例1解释：按(4,2)(4,2)排列是最优的，此时sum=(4−0)2+(2−4)2=20sum=(4−0)2+(2−4)2=20

示例2

输入

3

2 0 4

输出

36

说明

样例2解释：按(4,0,2)(4,0,2)排列是最优的，此时sum=(4−0)2+(0−4)2+(2−0)2=36sum=(4−0)2+(0−4)2+(2−0)2=36

示例3

输入

5

2 4 0 2 4

输出

52

备注:

1⩽n⩽1051⩽n⩽105，保证aiai为2/0/42/0/4中的数