牛客网 小a与204
链接:
https://ac.nowcoder.com/acm/contest/317/B
来源:牛客网
题目描述
小a非常喜欢204204204这个数字,因为′a′+′k′=204'a' + 'k' = 204′a′+′k′=204。
现在他有一个长度为nnn的序列,其中只含有2,0,42,0,42,0,4这三种数字
设aia_iai为序列中第iii个数,你需要重新排列这个数列,使得∑i=1n(ai−ai−1)2sum_{i = 1}^n (a_i - a_{i - 1})^2∑i=1n(ai−ai−1)2最大(公式的含义是:每个数与前一个数差的平方的和)
注意:我们默认a0=0a_0 = 0a0=0
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5+5;
int num[maxn];
int main()
{
int n;
while(cin>>n)
{
int sum=0;
int n4=0,n2=0,n0=0;
for(int i=0;i<n;++i)
{
cin>>num[i];
if(num[i]==4) n4++;
if(num[i]==2) n2++;
if(num[i]==0) n0++;
}
//cout<<n0<<n2<<n4<<endl; //
int cnt=n4<n0?n4:n0;
sum=cnt*16*2;
//cout<<sum<<endl; //
n4-=cnt;
n0-=cnt;
if(n4!=0) {
sum+=16;
n4--;
}
int len=n4>n0?n4:n0;
int aa=len<n2?len:n2;
sum+=aa*4*2;
len-=aa;
n2-=aa;
if(len>0 || n2>0)
{
sum+=4;
}
cout<<sum<<endl;
}
return 0;
}