2024.1.9 cf Hello 2024 1919D
解题思路
这题理解一下就是，找出数组中每一个比左数或右数大1的数，从大到小（体现优先队列）删除（体现链表），对访问过的数打个标记（vis），最后数组里的数要么被打过标记，要么是0.
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=200005;
int a[N],L[N],R[N],vis[N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin>>t;
while(t--)
{
int n;
priority_queue<pair<int,int>> pq;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
vis[i]=0;
}
for(int i=1;i<=n;i++)
{
if(i>1&&a[i]-1==a[i-1]&&!vis[i])
{
pq.push({a[i],i});
vis[i]=1;//打标记
}
if(i<n&&a[i]-1==a[i+1]&&!vis[i])
{
pq.push({a[i],i});
vis[i]=1;
}
}
R[0]=1,L[n+1]=n;
vis[0]=vis[n+1]=1;
for(int i=1;i<=n;i++)//数组模拟链表，L是前一个结点，R是后一个结点
{
L[i]=i-1;
R[i]=i+1;
}
for(int i=1;i<=n;i++)
{
if(pq.empty())break;
auto u=pq.top().second;//取出顶上的最大元素，从大到小删
int x=L[u],y=R[u];
if(x&&a[x]==a[u]-1||y!=n+1&&a[y]==a[u]-1)
{
pq.pop();
R[x]=y,L[y]=x;//删除结点（O(1)的复杂度）
vis[u]=1;
if(x&&y!=n+1)
{
if(a[y]==a[x]-1&&!vis[x])
{
pq.push({a[x],x});
vis[x]=1;
}
if(a[x]==a[y]-1&&!vis[y])
{
pq.push({a[y],y});
vis[y]=1;
}
}
}
}
bool ok=1;
int cnt=0;
for(int i=1;i<=n;i++)
{
if(a[i]&&!vis[i])ok=0;//数组里的数要么被标记过，要么是0
if(!a[i])cnt++;//0只能有一个
}
if(ok&&cnt==1)
{
cout<<"YES\n";
}
else cout<<"NO\n";
}
return 0;
}