牛客网 小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;
}
Last modification:November 21st, 2019 at 01:38 am
如果觉得我的文章对你有用,请随意赞赏