题解：P12880 [蓝桥杯 2025 国 C] 数字配对
Believe_in_dreams
·
·
题解
P12880[蓝桥杯 2025 国 C] 数字配对
给定长度为 n 的序列 a，取出若干数对 a_i,a_j 使得 i<j,~a_j=a_i+1，每一个数至多被取 1 次，求最多取多少对。
:::info[HintA]
**性质：** 如果当前最小值 $a_i=a_j=x,a_k=x+1,i<j<k$，则 $(j,k)$ 一定比 $(i,k)$ 更优。
:::
:::info[HintB]
**性质：** 如果当前最小值中下标最大的点为 $i$，且 $a_i=x,a_j=a_k=x+1,i<j<k$，则 $(i,k)$ 一定比 $(i,j)$ 更优。
:::
:::info[HintC]
考虑记录每一种数值的出现下标位置，按照数值从小到大贪心，在过程中用**双指针**维护信息。
:::
:::info[sol]
**贪心；双指针；对于配对问题考虑从数值角度贪心。**
**性质**如果当前最小值 $a_i=a_j=x,a_k=x+1,i<j<k$，则 $(j,k)$ 一定比 $(i,k)$ 更优。
**证明**
显然 $i,j$ 都只能与 $x+1$ 的位置组对。
$(i,k)$ 与 $(j,k)$ 对答案的贡献同为 $1$，但是 $i<j$，所以“能与 $j$ 成对的 $x+1$ 的位置”都能与 $i$ 成对。于是匹配 $(j,k)$，留下 $i$ 一定更优。
证毕。
**性质**如果当前最小值中下标最大的点为 $i$，且 $a_i=x,a_j=a_k=x+1,i<j<k$，则 $(i,k)$ 一定比 $(i,j)$ 更优。
**证明**
显然如果 $j,k$ 与值为 $x$ 的点都能成对，而 $j$ 比 $k$ 更能和值为 $x+2$ 的点成对，于是匹配 $(i,k)$，保留 $j$，一定更优。
证毕。
**做法**
综合上面的性质，算法应该很显然了。
考虑记录每一种数值的出现下标位置，按照数值从小到大贪心。
对于数值 $i+1$ 的下标最大的点（下标设为 $x$），不断找到数值 $i$ 中最后下标一个 $\ge x$ 的位置进行匹配。
**代码**
```cpp
const int N=1e6+5;
int n,ans;
vector<int>v[N];
signed main(){
n=read();
for(int i=1;i<=n;++i){
int x=read();
v[x].push_back(i);
}
for(int i=1;i<=1e6;++i){
while(v[i+1].size()){
while(v[i].size() and v[i].back()>=v[i+1].back())
v[i].pop_back();
if(!v[i].size())break;
++ans,v[i+1].pop_back(),v[i].pop_back();
}
}
write(ans);
return 0;
}
```
:::