[模拟賽]最佳位置(local)

相思豈雲遠，即席莫與同。

最佳位置

題面

​ 牛牛最近在研究一個問題，他将其稱之為“最佳位置”問題。 有 \(n\) 個座位從左到右排成一行，相鄰之間兩兩距離為 \(1\) ，編号從 \(1\) 到 \(n\)。 會有 \(m\) 個人按順序進來，選擇一個座位坐下，新來的人會計算每個位置，離最近的已被坐的座位的距離。

​ 新來的人會選擇距離最大的座位坐下，如果有多個，他會選擇編号最小的。如果場上都是空位置，來的人會選擇坐在位置 \(1\) 。

​ 如 \(xoooxoxx\), 離被坐的座位的距離就分别為 \(01210100\) ，如果這時候新來一個人，會選擇坐在位置 \(3\) ，變成 \(xoxoxoxx\) 。 當然，這些人也會離開，而空出目前的位置。 牛牛現在拿到了一張進入和離開的順序表，他想知道每個人落座時，會選擇什麼位置。

\(1\leq m\leq n\leq 10^9,1\leq m\leq 3\times 10^5\) 。

分析

其實這道題目的思路是非常顯然的。

我們考慮目前進來的人會選擇什麼樣的座位，假設此時座位 \(1\) 和 \(n\) 是有人的。

那麼他選擇的座位必定在某兩個位置之間，而顯然，當兩個位置确定的時候，這兩個位置中間的最佳位置也是确定的。

那麼我們就可以用一個單調隊列來封裝這個狀态，以距離為第一關鍵字， 以編号為第二關鍵字。

剩下的問題就是維護這個隊列。

對于一個人坐下的情況，那新增的狀态比較顯然。

假設我們選擇在座位 \(l\) 和座位 \(r\) 中間的座位 \(p\) 坐下，則 \((l,p)\) 和 \((r,p)\) 是我們新增加的兩個區間。

倘若一個人離開呢？

對于每一個有人的位置，我們可以記錄這個位置左邊第一個有人的座位，和右邊一個第一個有人的座位。

然後新增加的狀态也就是我們左邊第一個有人的位置和右邊第一個有人的位置組成的區間。

這些都是很順其自然的東西。

但是這道題惡心就惡心在我們需要特判一種情況。

也就是邊界情況。

假設位置 \(1\) 和位置 \(n\) 提前離開了怎麼辦？

顯然必然有一種狀态是離左邊界最近的有人的走位和離右邊界最近的有人的座位。

是以在上面寫的時候我們需要特判掉這一種情況，不能以同一種方式處理。

如果做到了這個細節那這道題就算做完了，感覺上思維難度不是很高，一道大模拟。

CODE

#include <bits/stdc++.h>
using namespace std; 
const int N=1e6+10,INF=1e9;
inline int read()
{
  int s=0,w=1;
  char ch=getchar();
  while(ch<'0'||ch>'9') { if(ch=='-') w*=-1; ch=getchar(); }
  while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
  return s*w; 
}
//記錄目前每個最佳位置的位置資訊和距離 
struct node{ 
  int l,r,p,dis; //記錄相鄰的兩個有人的座位以及他們的最大貢獻 
  friend bool operator < (const node &x,const node &y){ 
    if(x.dis>y.dis) return 0;
    else if(x.dis==y.dis) return x.p>y.p;
    else return 1;
  }
}; 
struct Seat{ int l,r; };
int n,m,cnt;
map<int,int> mp; //記錄人進來與否，且坐在哪個位置上 
map<int,bool> vis; //記錄每個座位上是否有人 
map<int,Seat> seat; //記錄距離該座位最近的兩個有人的座位 
priority_queue<node> q; 
int flag;
inline int id(int l,int r)
{
  int x=r-l-1,dis=x/2;
  if(x&1) return l+dis+1;
  else return l+dis;
}
inline int val(int l,int r)
{
  int x=r-l-1,dis=x/2;
  if(x&1) return dis;
  else return dis-1;
}
int main()
{
//  freopen("6.in","r",stdin);
//  freopen("local.out","w",stdout);
  n=read(),m=read(); 
  for(register int i=1;i<=2*m;i++){
    int x=read();
    if(mp.find(x)==mp.end()){  
      //最開始進來的兩個人肯定第一個坐1，第二個坐n 
      if(!flag) mp[x]=1,flag++,vis[1]=true,cnt++;
      else{
        if(flag==1){
          mp[x]=n,flag++,vis[n]=true,cnt++;
          seat[1].l=0,seat[1].r=n;
          seat[n].l=1,seat[n].r=n+1;
          q.push((node){1,n,id(1,n),val(1,n)});
        }
        else{
          while(!q.empty()){
            node now=q.top(); q.pop();
          //  cout<<now.l<<" "<<now.r<<" "<<now.p<<" "<<now.dis<<"\n";
            if(now.l>=1&&now.r<=n){ //正常情況 
              if(!vis[now.l]||!vis[now.r]) continue;
              int p=id(now.l,now.r);
              if(vis[p]) continue; //如果已經有人
              mp[x]=p,cnt++,vis[p]=true;
              seat[now.l].r=p,seat[now.r].l=p;
              seat[p].l=now.l,seat[p].r=now.r;
              //入隊 
              q.push((node){now.l,p,id(now.l,p),val(now.l,p)});
              q.push((node){p,now.r,id(p,now.r),val(p,now.r)});
            }
            else{
              if(now.l==0){ //填1 
                if(vis[1]) continue;
                if(!vis[now.r]) continue;
                mp[x]=1,cnt++,vis[1]=true;
                seat[1].l=0,seat[1].r=now.r;
                seat[now.r].l=1;
                q.push((node){1,now.r,id(1,now.r),val(1,now.r)}); 
              }
              else{ //填n 
                if(vis[n]) continue;
                if(!vis[now.l]) continue;
                mp[x]=n,cnt++,vis[n]=true;
                seat[n].l=now.l,seat[n].r=n+1;
                seat[now.l].r=n;
                q.push((node){now.l,n,id(now.l,n),val(now.l,n)});
              }
            }
            break; 
          }
        }
      }
    }
    else{ //考慮如何彈出 
      cnt--;
      vis[mp[x]]=false; //騰出座位
      if(!cnt){
        while(!q.empty()) q.pop(); //彈出所有 
        flag=0; continue; //全部人已經離開 
      } 
      int l=seat[mp[x]].l,r=seat[mp[x]].r;
      if(l>=1) seat[l].r=r;
      if(r<=n) seat[r].l=l;
      if(l>=1&&r<=n) q.push((node){l,r,id(l,r),val(l,r)}); //新入隊 
      else{
        if(l==0) q.push((node){0,r,1,r-2});
        if(r==n+1) q.push((node){l,n+1,n,n-l-1});
      }

    }
  }
  for(register int i=1;i<=m;i++) printf("%d\n",mp[i]);
  return 0;
}
      

作者：​​ ╰⋛⋋⊱๑落葉๑⊰⋌⋚╯​​