题解归档 - cf2232A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2232A
• 本地来源：problems/cf2232A/idea.md
• 题目链接：https://codeforces.com/contest/2232/problem/A
• 原始标题：2232A Convergence

思路

2232A Convergence

题意

有 (n) 个朋友位于整数坐标 (a_i)。每次 Alice 可同时呼叫两人，让他们走到 ([\min(a_i,a_j), \max(a_i,a_j)]) 内某个整数位置汇合；移动瞬间完成，之后可再次呼叫。求所有人到同一点的最少呼叫次数。

思路

一次呼叫只能让两个人汇合，但汇合点可在两人区间任意整数处，因此两人最终可视为「合并」到同一位置。

关键观察：将坐标排序后，若 (a_i \neq a_{n+1-i})，则第 (i) 小与第 (i) 大尚未配对，至少需要一次呼叫才能消除这一对差异。设这样的位置对有 (cnt) 个，则最少呼叫次数为 (\lfloor cnt/2 \rfloor)。

证明直觉：每次呼叫最多消除两个「未配对端点」（一左一右）；(cnt) 个不匹配端点至少需要 (cnt/2) 次两两配对。

算法

1. 排序 (a)
2. 统计 (i=1..n) 中 (a_i \neq a_{n+1-i}) 的个数 (cnt)
3. 输出 (cnt/2)

复杂度

• 时间：(O(n \log n)) 排序，(n \le 100)
• 空间：(O(n))

实现要点

• 排序后双端对比即可，无需模拟呼叫过程
• 样例 [1,1,1,2,2]：排序后仅 a[4]=2 与 a[2]=1 等三对不匹配？实际 (cnt=4)，答案 2

结果

• 本地样例通过
• 小数据 brute/gen 对拍验证

代码

来源：problems/cf2232A/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:12:00
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=105;
ll a[maxn+5],t,n,i,j,k,cnt;
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+n+1);
        cnt=0;
        for(i=1;i<=n;i++){
            if(a[i]!=a[n+1-i]) cnt++;
        }
        cout<<cnt/2<<"\n";
    }
    return 0;
}