小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的过程中计算结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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这里看标程的时候看到一个技巧，使用getchar()来统计204的数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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;
}因此第二种可以改成1
2
3
4
5
6inline 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;
}这样快了8ms…1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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;
}