「BalticOI 2023」Staring Contest题解

问题分析

我们需要通过两两比较来确定 $n$ 个选手的冷静能力值 $a_1, a_2, \ldots, a_n$。每次比较 ? i j 会返回 $\min(a_i, a_j)$ 的值。

关键观察：

• 最强的选手的值无法确定（因为所有与ta的比较都返回对方的值）
• 允许恰好一个值被低估（即输出值小于等于真实值，且最多一个不等于）

算法思路

核心思想

我们维护两个候选选手 $x$ 和 $y$，以及它们当前的估计值 $a[x]$ 和 $a[y]$。通过不断与其他选手比较来更新这两个候选者。

算法步骤

1. 初始化：随机打乱选手顺序，选择前两个作为初始候选 $x$ 和 $y$
2. 询问初始值：获取 $\min(a_x, a_y)$ 作为两者的初始估计值
3. 处理剩余选手：
   • 对于每个新选手 $p[i]$，与当前候选 $x$ 比较
   • 根据比较结果更新候选者和估计值

关键逻辑

设当前候选为 $x$ 和 $y$，新选手为 $v$：

• 如果 $\min(a_x, a_v) < a_x$：说明 $a_v$ 更小，直接记录该值
• 如果 $\min(a_x, a_v) > a_x$：说明 $a_x$ 被低估，更新候选者为 $x$ 和 $v$
• 如果相等：说明 $a_x = a_v$，需要重新确认候选者间的关系

代码实现详解

#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 1510
using namespace std;
mt19937_64 rnd(114514);  // 随机数生成器

int A[N];
int n, p[N], a[N];

// 询问函数：返回 min(a[x], a[y])
int ask(int x, int y) {
    cout << "? " << x + 1 << " " << y + 1 << '\n';
    fflush(stdout);
    cin >> x;
    return x;
}

int main() {
    cin >> n;
    
    // 初始化排列 [0, 1, ..., n-1]
    for (int i = 0; i < n; i++)
        p[i] = i;
    
    // 随机打乱选手顺序
    shuffle(p, p + n, rnd);
    
    // 选择前两个选手作为初始候选
    int x = p[0], y = p[1];
    a[x] = a[y] = ask(x, y);  // 获取初始估计值
    
    // 处理剩余选手
    for (int i = 2; i < n; i++) {
        int v = ask(x, p[i]);  // 比较当前候选x与新选手p[i]
        
        if (v < a[x]) {
            // 情况1：新选手的值更小，直接记录
            a[p[i]] = v;
        }
        else if (v > a[x]) {
            // 情况2：当前候选x的值被低估，更新候选者
            y = p[i];
            a[x] = a[y] = v;  // 更新两个候选者的估计值
        }
        else {
            // 情况3：值相等，需要重新确认候选者关系
            x = p[i];
            a[x] = a[y] = ask(x, y);  // 重新询问确认
        }
    }
    
    // 输出结果
    cout << "! ";
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    puts("");
    fflush(stdout);
    return 0;
}

算法正确性证明

1. 最多一个值被低估：算法中所有估计值都来自实际的 $\min$ 询问，因此 $b_i \leq a_i$ 恒成立。只有最强选手的值可能被低估。

2. 询问次数：初始需要 $1$ 次询问，之后每个选手最多需要 $2$ 次询问（一次比较，可能还需要一次确认），总询问数约为 $2n$，满足 $n + 25$ 的限制。

3. 随机化的作用：随机打乱避免了最坏情况，使得算法在期望情况下表现良好。

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$
• 询问复杂度：约 $2n$ 次询问

该算法高效地利用了每次比较的信息，通过维护候选对来逐步确定所有选手的冷静能力值，在满足题目限制的同时保证了正确性。