题解：P16798 [蓝桥杯 2026 国 B] Token 词元
Richard6666
·
·
题解
题意
给出 p 数组的要求，让我们推出 c 数组对 a 数组的限制，求出 a 数组总和最小值。
思路
$a_i$ 是正整数，又想要和最小，那就将初值设为 $1$。我们感性的认为，$a_i$ 的最大值不会很大，便可以采用**双向传递**的方法。
## 做法
1. **从左往右**推，处理递增约束。若 $c_i<c_{i+1}$，则将 $a_{i+1}$ 赋值为 $a_{i+1}$ 和 $a_i+1$ 中的最大值。
2. **从右往左**推，处理递减约束。若 $c_i>c_{i+1}$，则将 $a_i$ 赋值为 $a_i$ 和 $a_{i+1}+1$ 中的最大值。
## 证明
1. 处理递增或递减约束时，不会破坏其余约束。
2. 在 $c_i=c_{i+1}$ 时，不会无故拉高 $a_i$ 或 $a_{i+1}$ 的值。
3. 取较大值能同时满足两边的约束。
# 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=2e5+5;
int p[N],c[N],a[N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>p[i];
a[i]=1;//赋值
}
//计算c数组的值
for(int i=1;i<=n;i++){
if(i!=1&&p[i]>p[i-1]) c[i]++;
if(i!=n&&p[i]>p[i+1]) c[i]++;
}
//处理递增约束
for(int i=1;i<n;i++){
if(c[i]<c[i+1]) a[i+1]=max(a[i+1],a[i]+1);
}
//处理递减约束
for(int i=n-1;i>0;i--){
if(c[i]>c[i+1]) a[i]=max(a[i],a[i+1]+1);
}
//计算总和
int ans=0;
for(int i=1;i<=n;i++){
ans+=a[i];
}
cout<<ans<<endl;
return 0;
}
```