链接：https://codeforces.com/contest/2127

A. Mix Mex Max

算法：

    贪心、\(guess\)。

思路：

    直接 \(guess\) 得到只有除 \(-1\) 外全部元素相等且不为 \(0\)才可变成良序。

关键代码：

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a)
        cin >> x;

    if (ranges::count(a, -1) == n)
    {
        cout << "YES" << endl;
        return;
    }

    map<int, int> m;
    for (int i = 0; i < n; ++i)
        if (a[i] != -1)
            ++m[a[i]];

    if (m.size() == 1 && !m.count(0))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

B. Hamiiid, Haaamid… Hamid?

算法：

    贪心、博弈论。

思路：

    略。

关键代码：

void solve()
{
    ll n, x;
    string s;
    cin >> n >> x >> s;

    if (x == 1 || x == n || ranges::count(s, '.') == n)
    {
        cout << 1 << endl;
        return;
    }

    s = ' ' + s;

    ll pos1 = 0, pos2 = n + 1;
    for (int i = x - 1; i >= 1; --i)
    {
        if (s[i] == '#')
        {
            pos1 = i;
            break;
        }
    }

    for (int i = x + 1; i <= n; ++i)
    {
        if (s[i] == '#')
        {
            pos2 = i;
            break;
        }
    }

    cout << min(min(x, n - x + 1), max(pos1, n - pos2 + 1) + 1) << endl;
}

C. Trip Shopping

算法：

    贪心、排序、博弈论。

思路：

    可以发现每次操作价值只会增加或者不变。

    因为当阿里选择了一对下标后，如果交换和会让价值变小，那么巴赫曼就不会交换，既保持原样。

    此时不难想到阿里的最优策略是选择一对 \((i, j)\) 进行一次交换后，后面一直选择这对。

    对于选择的这一对的最优策略就是选择增量最小的一对。

    将 \({a[i], b[i]}\) 作为二元组存储到 \(v\) 中，对 \(v\) 进行排序，最小增量一定是相邻的两对。

关键代码：

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<pii> a(n);
    for (auto &[x, y] : a)
        cin >> x;
    for (auto &[x, y] : a)
        cin >> y;

    ranges::sort(a);

    ll ans = 0;
    for (int i = 0; i < n; ++i)
        ans += abs(a[i].first - a[i].second);

    ll minn = INT_MAX;
    for (int i = 0; i < n - 1; ++i)
    {
        vector<ll> t = {a[i].first, a[i].second, a[i + 1].first, a[i + 1].second};

        ranges::sort(t);

        minn = min(minn, (t[3] - t[0]) + (t[2] - t[1]) -
                             abs(a[i].first - a[i].second) - abs(a[i + 1].first - a[i + 1].second));
    }

    cout << ans + minn << endl;
}

D. Root was Built by Love, Broken by Destiny