牛牛排队伍

标签： 双向链表

难度： 适中

思路：

因为按从小到大顺序排队，因此，只需两个数组pre[]和ne[]维护该位置之前和之后排的人即可。

技巧：

竞赛中链表可用数组实现，无需再创建结构体，再分配空间，销毁空间等一系列操作。

示例1：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int pre[N],ne[N],data[N];

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,k,opt,x;
	cin>>n>>k;
	
	for(int i=1;i<=n;i++)
	{
		if(i==1)
			pre[i]=0;
		else
			pre[i]=i-1;
		
		if(i==n)
			ne[i]=0;
		else
			ne[i]=i+1;
		
	}
	
	while(k--)
	{
		cin>>opt>>x;
		if(opt==1)
		{
			ne[pre[x]]=ne[x];
			pre[ne[x]]=pre[x];
		}
		else{
			if(pre[x]==0)
				cout<<0<<endl;
			else
				cout<<pre[x]<<endl;
		}
	}
		
	return 0;
}

示例2：

#include<bits/stdc++.h>
using namespace std;
 
int n, k;
 
int main() {
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin >> n >> k;
  set<int> st;
  for (int i = 0; i <= n; ++i) st.insert(i);
  while (k--) {
    int op, x;
    cin >> op >> x;
    if (op == 1) {
      st.erase(x);
    }
    else {
      auto it = st.lower_bound(x);
      --it;
//       if (it == st.end()) cout << "0" << endl; else
      cout << *it << '\n';
    }
  }
}