题解 | #小红的不动点分配#

关键思路

1. 不动点的形成条件
   由于每组的大小为 ，位置索引范围为 到 。因此，只有值在 范围内的元素才可能在某个位置 形成不动点（即 ）。值大于 的元素无法形成任何不动点。

2. 最大不动点贡献分析
   对于每个值 （）：

   • 若该值在输入中出现 次，则最多可以为两组分别提供一个 （即在第一组的第 位和第二组的第 位各放一个 ），从而形成 2 个不动点。
   • 因此，每个 的最大贡献为 。

3. 全局最优策略
   将所有 的 累加，即可得到两组不动点数量之和的最大值。

算法步骤

1. 统计频率
   遍历输入的 个元素，统计每个值 （）的出现次数。

2. 计算最大和
   遍历 到 ，将每个 的贡献 累加到结果中。

3. 输出结果
   返回累加结果。

代码实现

#include <bits/stdc++.h>
using namespace std;
#define f(i, a, b) for (ll i = a; i <= b; i++)
#define fr(i, a, b) for (ll i = a; i >= b; i--)

typedef long long ll;
const int N = 1e5 + 10;
const int Mod = 1e9 + 7;

void solves(){
    ll n;
    cin >> n;

    ll cnt = 0;
    vector<ll> a(2 * n,0);

    f(i,1,2 * n){
        ll x;
        cin >> x;
        if(x <= n) a[x]++;
    }

    for(auto i : a){
        cnt += min(i,2ll);
    }

    cout << cnt << "\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    //cin >> T;
    while (T--)
    {
        solves();
    }

    return 0;
}

复杂度分析

• 时间复杂度：
  遍历 个元素进行计数（），再遍历 个可能的值计算结果（），总体线性时间。

• 空间复杂度：
  使用长度为 的数组 cnt 存储频率，空间占用与 成正比。