题解：P14917 [GESP202512 五级] 数字移动
题意
给定一个长度为 \(N\) 的正整数序列 \(A\)，每个数字恰好出现两次。每次操作可以选择一个数字移动到任意位置，花费的体力等于该数字的值。目标是让所有相同的数字相邻，同时要求每次操作花费的体力不超过 \(x\)。求最小化 \(x\)。
数据范围与约定
对于所有测试点，\(1 \le N,A_i \le 10^5\)。
解题思路
1.问题转化
显然，根据题意，可以转化为：
能否只移动 \(\le x\) 的 \(A_i\)，使得序列 \(A\) 配对相邻。
2.核心发现
移除掉 \(\le x\) 的 \(A_i\) 后，剩下的序列中的每个数字必须保证两两相邻。
3.判断方法
要判断某个 \(x\) 是否可行：
\(1.\) 从原序列中提取所有 \(A_i > x\) 的数字。
\(2.\)检查这些数字是否满足：每个数字都与相邻的相同数字配对。
更形式化地，设提取后的序列为 \(B\)，长度为 \(m\)，则：
对于所有的 \(i\)，要满足 \(B_i = B_{i - 1}\) 或 \(B_i = B_{i+1}\)。
4.二分优化
正确性分析
- 如果 \(x\) 可行，那么所有更大的 \(x\) 也可行。
- 如果 \(x\) 不可行，那么所有更小的 \(x\) 也不可行。
显然，答案具有单调性，可以进行二分。
二分的上界和下界
显然，下界为 \(x = 1\)；而上界为 \(x=\max\{A_i\}\)，因为 \(x=\max\{A_i\}\) 时所有元素均可移动。
实现
时间复杂度可行性分析
每次判断：\(O(n)\)；
二分答案：\(O(\log \max\{A_i\})\)；
总复杂度 \(O(n \log \max \{A_i\})\)
该复杂度对于 \(N \le 10^5\) 可行。
Code
#include <bits/stdc++.h>
using namespace std;
/*====================*/
using ll=long long;
/*====================*/
#define endl "\n"
/*====================*/
const int N=1e5+10;
/*====================*/
int a[N];
/*====================*/
int n;
/*====================*/
int temp[N];
/*====================*/
bool Check(int mid)
{int tot=0;for(int i=1;i<=n;i++){if(a[i]<=mid)continue;temp[++tot]=a[i];}for(int i=1;i<=tot;i++){if(temp[i]!=temp[i-1]&&temp[i]!=temp[i+1])return false;}return true;
}
/*====================*/
void Solve()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i];int l=1,r=*max_element(a+1,a+n+1);int ans=0;while(l<=r){int mid=(l+r)>>1;if(Check(mid))r=mid-1,ans=mid;else l=mid+1;}cout<<ans<<endl;
}
/*====================*/
int main()
{freopen("in.txt","r",stdin);ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);Solve();return 0;
}