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

A. Divisible Permutation

算法：

构造。

思路：

打表找规律。

关键代码：

void miyan()
{
    int n;
    cin >> n;

    if (n & 1)
    {
        for (int i = n / 2 + 1; i >= 1; --i)
        {
            if (i > 1)
                cout << i << ' ' << n + 2 - i << ' ';
            else
                cout << 1 << ' ';
        }
    }
    else
    {
        for (int i = n / 2 + 1; i <= n; ++i)
            cout << i << ' ' << n + 1 - i << ' ';
    }
    cout << endl;
}

B. Seats

算法：

贪心，分块计数。

思路：

根据 \(1\) 对字符串进行分块，计算每块最小放置 \(1\) 的个数。

关键代码：

void miyan()
{
    int n;
    string s;
    cin >> n >> s;

    int ans = 0;
    int cnt = 0;
    bool ok = 0;
    for (int i = 0; i < n; ++i)
    {
        if (s[i] - '0')
        {
            ans += (cnt + 1 - ok) / 3;
            ok = 1;
            cnt = 0;
        }
        else
            ++cnt;
    }

    if (cnt && ok)
        ans += (cnt + 1) / 3;
    else if (cnt)
        ans += (cnt + 2) / 3;

    cout << ans + ranges::count(s, '1') << endl;
}

C. Restricted Sorting

算法：

贪心，二分。

思路：

显然当数组已经是按非降序排序时，答案为 \(-1\)。

定义 \(a\) 数组为原数组，\(b\) 数组为按非降序排序的 \(a\) 数组。

考虑二分答案，如果 \(a_i\) 和 \(b_i\) 的差的绝对值小于 \(mid\) 则直接交换，否则找一个中间锚点，作为 \(a_i\) 与 \(b_i\) 交换的中间节点，显然这个中间锚点选择数组最大值或最小值，判断 \(a_i\) 与锚点的差的绝对值是否大于等于 \(mid\) 即可。

关键代码：

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

    auto b = a;
    ranges::sort(b);

    if (a == b)
    {
        cout << -1 << endl;
        return;
    }

    ll maxx = ranges::max(a);
    ll minn = ranges::min(a);

    auto check = [&](ll x) -> bool
    {
        for (int i = 0; i < n; ++i)
        {
            if (a[i] == b[i] || abs(a[i] - b[i]) >= x || abs(a[i] - maxx) >= x || abs(a[i] - minn) >= x)
                continue;

            return 0;
        }

        return 1;
    };

    ll l = 1, r = 2e9;
    while (l < r)
    {
        ll mid = l + r + 1 >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }

    cout << l << endl;
}

D. Shortest Statement Ever

还没补。