[COCI 2007/2008 #3] CETIRI

题意

原来有 4 个数，排序后构成一个等差数列。
现在丢失了其中一个，只剩下 3 个数，顺序还被打乱。
要求找出那个缺失的数。

思路

先看一个可以直接验证想法的朴素解：

枚举一个可能的第四个数 x，把它和原来三个数放在一起排序，检查四个数能不能构成等差数列。

cpp

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// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

int a[3];

bool check(int x) {
    int b[4];
    for (int i = 0; i < 3; i++) {
        b[i] = a[i];
    }
    b[3] = x;
    sort(b, b + 4);
    return b[1] - b[0] == b[2] - b[1] && b[2] - b[1] == b[3] - b[2];
}

void solve() {
    // 为了与正式解保持一致：
    // 如果有多个合法答案，优先输出数值更大的那个。
    int ans = -1000000000;
    for (int x = -1000; x <= 1000; x++) {
        if (check(x)) {
            ans = x;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> a[0] >> a[1] >> a[2];
    solve();

    return 0;
}

这个写法虽然直观，但没有抓住本题真正的结构。
关键其实只在排序后的两个相邻差值上。

设排序后是：

a0 <= a1 <= a2

那么只看：

d1 = a1 - a0
d2 = a2 - a1

下面这张表展示了剩下三个数可能出现的形态：

原来保留的三项	排序后差值
第 1、2、3 项	`d, d`
第 1、2、4 项	`d, 2d`
第 1、3、4 项	`2d, d`

表格右列表示：排序后只会出现“差值相等”或“一个差值更大”的情况。
如果两个差值相等，说明这三个数本身已经成等差，按样例风格补右边那个后继项即可。
如果两个差值不相等，缺失的数一定就在较大的那个空档中间。

因此正式做法是：

先排序；
算 d1 和 d2；
若 d1 == d2，输出 a2 + d1；
若 d1 < d2，输出 a1 + d1；
若 d1 > d2，输出 a0 + d2。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

int a[3];

void solve() {
    sort(a, a + 3);

    int d1 = a[1] - a[0];
    int d2 = a[2] - a[1];

    // 三个数本身已成等差时，按样例风格补在右侧。
    if (d1 == d2) {
        cout << a[2] + d1 << '\n';
        return;
    }

    if (d1 < d2) {
        cout << a[1] + d1 << '\n';
    } else {
        cout << a[0] + d2 << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> a[0] >> a[1] >> a[2];
    solve();

    return 0;
}

复杂度

时间复杂度是 $O(1)$ ，空间复杂度也是 $O(1)$ 。

总结

这题的重点不是暴力枚举第四个数，而是看清排序后的结构：

等差已经成立时，直接补后继项；
不等差时，答案就在较大的空档中间。

[COCI 2007/2008 #3] CETIRI

目录

题意

思路

代码

复杂度

总结