CF1293A - ConneR and the A.R.C. Markland-N 题解

这道题虽然是 Div2A,但是听说很多选手在比赛时思考了很久,甚至出现了比赛开始后 5min 左右排名榜第一面的许多人都是 AC 了 B 而没有通过 A...遂写了这篇题解.
首先可以确定的是,显然 \(O(tn)\) 的暴力做法无法通过此题,因为 \(t\) 和 \(n\) 已经分别达到了 \(10^3\) 和 \(10^9\) 的级别,纵使 CF 的评测机跑得飞快也无法 AC.
然后就有了一个桶排的思想,但是显然会 MLE...然而,这个世界上有一个叫 map(或者set)的东西...
于是,就 AC 了...
时间复杂度 \(O(tk\log k)\).

Code:

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
int t,n,s,k;
map<int,bool> mp;
void rd(int&);
void wt(int);
int main() {
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    rd(t);
    while (t--) {
        rd(n),rd(s),rd(k);
        for (int i=1;i<=k;i++) {
            int x;
            rd(x);
            mp[x]=true;
        }
        for (int i=0;;i++)
            if ((!mp[s+i]&&s+i<=n)||(!mp[s-i]&&s-i>0)) {
                wt(i);
                putchar('\n');
                break;
            }
        mp.clear();
    }
    return 0;
}
void rd(int& x) {
    x=0;
    char ch=getchar();
    while (!isdigit(ch))
        ch=getchar();
    while (isdigit(ch)) {
        x=x*10+ch-48;
        ch=getchar();
    }
}
void wt(int x) {
    if (x>9)
        wt(x/10);
    putchar(x%10+48);
}

CF1293A - ConneR and the A.R.C. Markland-N 题解

原文：https://www.cnblogs.com/Xray-luogu/p/12238858.html