- 题目来源于:牛客 | 小 a 与 "204"
题目大意 | 小 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);
- }