本文主要是介绍1B.小a与204（C++），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
小a与"204"（C++）
点击做题网站链接
题目描述
小a非常喜欢204这个数字，因为′a′+′k′=204。
现在他有一个长度为n的序列，其中只含有2,0,4这三种数字
设ai为序列中第i个数，你需要重新排列这个数列，使得 ∑ i = 1 n ( a i − a i − 1 ) 2 \sum_{i=1}^n (a_i−a_{i−1})^2 ∑i=1n(ai−ai−1)2最大(公式的含义是：每个数与前一个数差的平方的和)
注意：我们默认 a 0 a_0 a0=0
输入描述:
第一行一个整数n
接下来一行n个整数，第i个数表示 a i a_i ai
输出描述:
输出一个整数，表示 ∑ i = 1 n ( a i − a i − 1 ) 2 \sum_{i=1}^n (a_i−a_{i−1})^2 ∑i=1n(ai−ai−1)2的最大值
示例1
输入
2
2 4
输出
20
说明
样例1解释：按(4,2)排列是最优的，此时 s u m = ( 4 − 0 ) 2 + ( 2 − 4 ) 2 = 20 sum=(4−0)^2+(2−4)^2=20 sum=(4−0)2+(2−4)2=20
示例2
输入
3
2 0 4
输出
36
说明
样例2解释：按(4,0,2)排列是最优的，此时 s u m = ( 4 − 0 ) 2 + ( 0 − 4 ) 2 + ( 2 − 0 ) 2 = 36 sum=(4−0)^2+(0−4)^2+(2−0)^2=36 sum=(4−0)2+(0−4)2+(2−0)2=36
示例3
输入
5
2 4 0 2 4
输出
52
备注:
1 ⩽ n ⩽ 1 0 5 1⩽n⩽10^5 1⩽n⩽105，保证 a i a_i ai为2/0/4中的数
题目解析：
贪心算法
一个显然的构造策略是首先放置4, 0, 4, 0，直到其中一个用光。
接下来如果4多余，那么可以按4, 0, 4, 0, … , 4, 2, 4, 2, …(先4后2)的方法构造
如果0多余，可以按照4, 0, 4, 0 … 4, 0, 2, 0, 2 …(先2后0)的方法构造
实际上此题还可以推广到更一般的情况，也就是第一个位置放最大的，第二个位置放最小的，第三个位置放第二大的以此类推，这种思路写起来也会更简单一些。
所以，我们只需要记录下2/0/4分别出现的次数，并且每次找到记录匹配就行。其实这样我们可以把数字从大到小排序，并且使用两个标记，一个从前向后依次位移，一个从后向前依次位移，直到两个重合结束，那么前面那个标记肯定先计数4，后面那个标记肯定先计数0，等4和0用完，自然就剩2了。
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;bool com(int a,int b) { return a>b; }
const int N = 1e5 +5;int main()
{long long int n,temp=0;int a[N];cin >> n;for(int i=0;i<n;++i) cin >> a[i];sort(a,a+n,com);if(n==1)//如果只有一个数字{temp += a[0]*a[0];cout << temp << endl;return 0;}int Count = 0;for(int i=0,j=n-1;i<j;)//i，j两个标记位移，当i<j时执行循环，特别注意i和j在什么特殊的情况下会+1，而不是每次都+1{if( Count!=0 )//如果是不是第一次进来{temp += pow((a[i]-a[j]),2);if( Count%2==1 ) ++i;if( Count%2==0 ) --j;}else//如果是第一次进来{temp += a[0]*a[0];}Count++;}cout << temp << endl;return 0;
}
这篇关于1B.小a与204（C++）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
