一层一层删
链表模拟
最开始写的是一个一个删的 WA
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que;
const double EPS = 1.0e-8;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e5 + ;
const int maxm = ;
int a[maxn];
int pre[maxn], last[maxn];
int visit[maxn];
queue<int> que;
int main()
{
int t ;
cin >> t;
while (t--)
{
mem(visit, );
pre[] = -, last[] = ;
int n;
cin >> n;
a[] = -;
a[n + ] = INT_MAX;
for (int i = ; i <= n; i++)
{
scanf("%d", &a[i]);
pre[i] = i - , last[i] = i + ;
}
int flag = ;
for (int i = ; i < n; i++)
if (a[i] <= a[i + ])
{
flag = ;
}
if (!flag)
{
cout << << endl;
continue;
}
for (int i = ; i <= n; i++)
{
if (a[pre[i]] > a[i] || a[last[i]] < a[i])
{
que.push(pre[i]);
visit[i] = ;
pre[last[i]] = pre[i];
last[pre[i]] = last[i];
}
}
while (!que.empty())
{
int now = que.front();
que.pop();
if (!visit[now])
{
continue;
}
if (a[pre[now]] > a[now] || a[last[now]] < a[now])
{
que.push(pre[now]);
visit[now] = ;
pre[last[now]] = pre[now];
last[pre[now]] = last[now];
}
}
int sum = ;
for (int i = ; i <= n; i++)
if (visit[i])
{
sum++;
}
cout << sum << endl;
if (sum)
{
for (int i = ; i <= n; i++)
if (visit[i])
{
printf("%d ", a[i]);
}
cout << endl;
}
}
}
正解:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 1e5 + ;
int que[maxn], a[maxn], pre[maxn], suf[maxn], n, top;
int main()
{
int _;
cin >> _;
while(_--)
{
top = ;
scanf("%d", &n);
for(int i = ; i <= n; i++)
{
pre[i] = i-;
suf[i] = i+;
scanf("%d", &a[i]);
que[top++] = i;
}
suf[] = ;
int ans = n, flag = ;
while() //一轮一轮的删， 如果没有改动过，说明都是有序的了
{
int cnt = , cur = , flag = ;
while(cur < top) //当前这一轮
{
int p = que[cur], num = ;
while(suf[p] <= n && a[p] > a[suf[p]]) //把一个连续的删掉
{
flag = ;
num++;
p = suf[p];
}
if(num)
{
ans -= num+;
suf[pre[que[cur]]] = suf[p]; //维护链表，使其联通
pre[suf[p]] = pre[que[cur]];
que[cnt++] = pre[que[cur]];
}
while(que[cur] <= p && cur < top) //修改当前指针
cur++;
}
top = cnt;
if(!flag) break; //没有就跳出
}
printf("%d\n", ans);
int cur = ;
while(cur <= n)
{
if(cur)
printf("%d ",a[cur]);
cur = suf[cur];
}
puts("");
}
return ;
}