【贪心】小A与204

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

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

输入描述:

第一行一个整数n
接下来一行n个整数,第i个数表示ai

输出描述:

输出一个整数,表示ni=1(aiai1)2的最大值
示例1

输入

复制

2
2 4

输出

复制

20

说明

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

输入

复制

3
2 0 4

输出

复制

36

说明

样例2解释:按(4,0,2)排列是最优的,此时sum=(40)2+(04)2+(20)2=36sum=(4−0)2+(0−4)2+(2−0)2=36
示例3

输入

复制

5 
2 4 0 2 4

输出

复制

52

取数组前后差值最大的元素,此时结果最优

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int x[100005], a, b, n;
int main()
{
    ll ans = 0;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
        scanf("%d",&x[i]);
    sort(x+1,x+n+1);
    for(int i = 0; i <= n/2; i++)
        ans += (x[n-i]-x[i])*(x[n-i]-x[i])+(x[i+1]-x[n-i])*(x[i+1]-x[n-i]);

    printf("%lld", ans);
    return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

3 × 2 =