小a与204

链接：https://ac.nowcoder.com/acm/contest/317/B
来源：牛客网

题目描述
小a非常喜欢204
这个数字，因为′a′+′k′=204。
现在他有一个长度为n的序列，其中只含有2,0,4这三种数字
设ai为序列中第i个数，你需要重新排列这个数列，使得∑ni=1(ai−ai−1)2最大(公式的含义是：每个数与前一个数差的平方的和)
注意：我们默认a0=0

输入描述:

第一行一个整数n
接下来一行n个整数，第i个数表示ai

输出描述:
输出一个整数，表示∑ni=1(ai−ai−1)2
的最大值

示例1
输入
2
2 4

输出
20

说明

样例1解释：按(4,2)

排列是最优的，此时sum=(4−0)2+(2−4)2=20

示例2
输入
3
2 0 4

输出
36

说明

样例2解释：按(4,0,2)

排列是最优的，此时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中的数

这题主要是考贪心和模拟，可以观察出，应该先将4和0穿插着排列，如果还有0的话就把2和0穿插排列，如果0没有了但有4的话就把2和4穿插排列，我们的程序就是要把这个过程模拟出来。

• 第一种，直接在排列204的过程中计算结果

#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int n, temp;
    int t, z, f;
    t = z = f = 0;
    long long result = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &temp);
        if (temp == 2)
            t++;
        else if (temp == 0)
            z++;
        else
            f++;
    }
    temp = 0;//temp是当前排列的最后一个数
    while (t != 0 || z != 0 || f != 0) {
        if (temp == 0) {
            if (f != 0) {
                result += 16;
                f--;
                temp = 4;
            }
            else if (t != 0) {
                result += 4;
                t--;
                temp = 2;
            }
            else
                z--;
        }
        else if (temp == 4) {
            if (z != 0) {
                result += 16;
                z--;
                temp = 0;
            }
            else if (t != 0) {
                result += 4;
                t--;
                temp = 2;
            }
            else
                f--;
        }
        else if (temp == 2) {
            if (z != 0) {
                result += 4;
                z--;
                temp = 0;
            }
            else if (f != 0) {
                result += 4;
                f--;
                temp = 4;
            }
            else
                t--;
        }
        if (f == 0 && z == 0 && t != 0) {
            result += 4;
            break;
        }
    }
    cout << result;
    return 0;
}

• 第二种,先进行排列在计算最后的sum

#include<bits/stdc++.h>
 
using namespace std;
const int MAX = 1e5 + 10;
int a[MAX];
 
int main()
{
    int n, temp;
    int s[6] = { 0 };
    long long res = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &temp);
        s[temp]++;
    }
    a[0] = 0;
    temp = 1;
    while (s[4] != 0 && s[0] != 0) { //先对4和0进行排列
        a[temp++] = 4; a[temp++] = 0;
        s[4]--; s[0]--;
    }
    if (s[0] != 0) {    //如果还剩下0
        while (s[2] != 0 && s[0] != 0) {  //2和0进行排列
            a[temp++] = 2; a[temp++] = 0;
            s[2]--; s[0]--;
        }
        while (s[2] != 0) {    //还剩下2
            a[temp++] = 2;
            s[2]--;
        }
        while (s[0] != 0) {    //还剩下0
            a[temp++] = 0;
            s[0]--;
        }
    }
    else if (s[4] != 0) {      //如果还剩下4
        while (s[4] != 0 && s[2] != 0) {    //对4和2进行排列
            a[temp++] = 4; a[temp++] = 2;
            s[2]--; s[4]--;
        }
        while (s[4] != 0) {    //还剩下4
            a[temp++] = 4;
            s[4]--;
        }
        while (s[2] != 0) {    //还剩下2
            a[temp++] = 2;
            s[2]--;
        }
    }
    else {
        while (s[2] != 0) {    //只剩下2
            a[temp++] = 2;
            s[2]--;
        }
    }
    for (int i = 0; i < temp - 1; i++)
        res += (a[i + 1] - a[i])*(a[i + 1] - a[i]);
    cout<<res;
    return 0;
}

这里看标程的时候看到一个技巧，使用getchar()来统计204的数量

inline int read() {
	char c = getchar(); int x = 0, f = 1;
	while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}

因此第二种可以改成

#include<bits/stdc++.h>
 
using namespace std;
const int MAX = 1e5 + 10;
int a[MAX];
 
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
 
int main()
{
    int n,temp;
    int s[6] = {0};
    long long res=0;
    cin >> n;
    for (int i = 0; i < n; i++)
        s[read()]++;
    a[0] = 0;
    temp = 1;
    while (s[4] != 0 && s[0] != 0) {
        a[temp++] = 4;a[temp++] = 0;
        s[4]--; s[0]--;
    }
    if (s[0] != 0) {
        while (s[2] != 0 && s[0] != 0) {
            a[temp++] = 2; a[temp++] = 0;
            s[2]--; s[0]--;
        }
        while (s[2] != 0) {
            a[temp++] = 2;
            s[2]--;
        }
        while (s[0] != 0) {
            a[temp++] = 0;
            s[0]--;
        }
    }
    else if (s[4] != 0) {
        while (s[4] != 0 && s[2] != 0) {
            a[temp++] = 4; a[temp++] = 2;
            s[2]--; s[4]--;
        }
        while (s[4] != 0) {
            a[temp++] = 4;
            s[4]--;
        }
        while (s[2] != 0) {
            a[temp++] = 2;
            s[2]--;
        }
    }
    else {
        while (s[2] != 0) {
            a[temp++] = 2;
            s[2]--;
        }
    }
    for (int i = 0; i < temp-1; i++)
        res += (a[i + 1] - a[i])*(a[i + 1] - a[i]);
    cout << res;
    return 0;
}

这样快了8ms…