[CF1450F] The Struggling Contestant

[CF1450F] The Struggling Contestant - 构造

Description

求一个 (1..n) 的全排列 (p)，代价定义为满足 (|p_{i+1}-p_i|>1) 的 (i) 的个数。需要满足 (a_{p_i} e a_{p_{i+1}} forall 1leq i< n)

Solution

对于每对连续相同的数，必须在这里断开，因此如果有 k 对，就需要切至少 k 次

但如果出现这样的情况，就不够了

1--1, 1--1, 1--2

观察发现，如果一个数作为端点出现的次数超过 (k+2)，那么我们需要额外切若干次

但显然不会有两个数同时超过 (k+2)，所以我们只需要考虑最大数即可

如果一个数在原数组中的出现次数大于总数的一半（上取整），那么一定无解（例子 11111222,1111222）

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 2);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int k = 0;
    for (int i = 1; i < n; i++)
        if (a[i] == a[i + 1])
            ++k;
    map<int, int> mp, mm;
    for (int i = 1; i <= n; i++)
        mm[a[i]]++;
    int xx = 0;
    for (auto [x, y] : mm)
        xx = max(xx, y);
    if (xx > (n + 1) / 2)
    {
        cout << -1 << endl;
        return;
    }
    mp[a[1]]++;
    mp[a[n]]++;
    for (int i = 1; i < n; i++)
        if (a[i] == a[i + 1])
            mp[a[i]]++, mp[a[i + 1]]++;
    int mx = 0;
    for (auto [x, y] : mp)
        mx = max(mx, y);
    cout << max(k, mx - 2) << endl;
}

signed main()
{
    ios::sync_with_stdio(false);

    int t;
    cin >> t;

    while (t--)
    {
        solve();
    }
}