鏈接：https://ac.nowcoder.com/acm/contest/317/B
來源：牛客網(wǎng)

時(shí)間限制：C/C++ 1秒，
其他語言2秒 空間限制：
C/C++ 262144K，其他語言524288K 64bit IO Format: %lld
題目描述 小a非常喜歡 204 這個(gè)數(shù)字，因?yàn)?′ a ′ + ′ k ′ = 204 。 現(xiàn)在他有一個(gè)長度為 n 的序列，其中只含有 2,0,4這三種數(shù)字 設(shè) ai為序列中第 i個(gè)數(shù)，你需要重新排列這個(gè)數(shù)列，使得 2 ∑i=1n(ai?ai?1)^2最大
(公式的含義是：每個(gè)數(shù)與前一個(gè)數(shù)差的平方的和) 注意：我們默認(rèn) a0=0

輸入描述: 第一行一個(gè)整數(shù) n
接下來一行 n 個(gè)整數(shù)，第 i 個(gè)數(shù)表示 ai
輸出描述: 輸出一個(gè)整數(shù)，表示 ∑i=1n(ai?ai?1)^2的最大值
示例1
輸入2
2 4
輸出 20
說明
樣例1解釋：按 (4,2)排列是最優(yōu)的，此時(shí) sum=(4?0)^2 + (2?4)^2=20
示例2
輸入 3
2 0 4
輸出 36
說明 樣例2解釋：按 (4,0,2)排列是最優(yōu)的，
此時(shí)sum=(4?0)^2 + (0?4)^2 + (2?0)^2=36
示例3
輸入
5
2 4 0 2 4
輸出
52
備注: 1?n?105，保證 ai為2/0/4中的數(shù)
/*
貪心
排列方式，加一個(gè)0，sort一下，先取最小的，再取最大的，之后取第二小的，然后第二大的組成的序列為所求序列，然后直接算OK
*/

#include <stdio.h> #include <algorithm> using namespace std; int a[100005],b[100005]; int main() {int n;while(~scanf("%d",&n)){for(int i = 1; i <= n; i++){scanf("%d",&a[i]);}sort(a+1,a+n+1);int k = 0;for(int i = 0, j = n; i <= n/2; i++,j--){b[k++] = a[i];if(i != j)b[k++] = a[j];}double sum = 0;for(int i = 1; i < k; i++){sum += (b[i] - b[i-1])*(b[i] - b[i-1]);}printf("%.0lf\n",sum);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的小a与204（牛客寒假算法集训营1题目B）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。