题目大意 | 小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);
}