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