題目

1

2

代碼

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct node{int pre,//上一個水果塊(對于水果就是上個水果)l,//塊開始的序號，左邊界 d,//塊類型，0/1id,//水果序號 r,//塊結束的序號，右邊界 next;//下一塊(下個水果)node(){d=-1;id=-1;};//空參數構造函數 node(int px,int lx,int vx,int rx,int nx){//構造水果塊。//上一塊，左邊界，水果類型，右邊界，下一塊 pre=px,l=lx,d=vx,r=rx,next=nx;};node(int px,int idx,int nx){//構造一個水果//上一個水果，水果序號，下一個水果 pre=px,id=idx,next=nx;}; bool isempty(){//判定塊是否空了(已挑空該塊水果) if(l>r)return 1;else return 0;} 
}k[N],f[N];//N塊,N水果 
int n,//水果數m=0;//塊序號 
void view(int x){cout<<"果籃"<<x<<endl;for(int i=k[0].next;k[i].d!=-1;i=k[i].next){//遍歷所有塊 cout<<i<<"("<<k[i].d<<")";for(int j=k[i].l;j!=k[k[i].next].l;j=f[j].next)//遍歷該塊所有水果 cout<<f[j].id<<" ";cout<<"\t";}cout<<endl;
}
int main(){//freopen("data.cpp","r",stdin);int l=0,//左邊界 r,//右邊界 x=-1,//本塊水果類型 x2;//后塊水果類型 scanf("%d",&n);for(int i=1;i<=n+1;i++){//遍歷所有水果。多循環一次,用以確認最后一塊 if(i<=n)scanf("%d",&x2);else x2=-2;//最后一塊,跟第一塊-1不一樣(全空后不合并)f[i]=node{i-1,i,i+1};//建立本水果(鏈表) if(x!=x2){//本水果跟上一水果不一樣，那前面就是一個塊 r=i-1;//上一塊的右邊界 k[m]=node{m-1,l,x,r,m+1};//建立上一塊(鏈表) l=i,x=x2;//本塊的左邊界和水果類型 m+=1;//本塊序號 }}k[m]=node{m-1,n+1,-2,n+1,m+1};//尾塊//view(0);while(k[0].next!=m){//第一個空塊的下一個不是最后一個空塊就繼續 for(int i=k[0].next;i!=m+1;i=k[i].next){//遍歷所有塊，包括最后一個空塊 if(k[i].d!=-2){//非最后一個空塊 //cout<<"輸出"<<i<<"("<<k[i].v[0]<<")\n";cout<<f[k[i].l].id<<" ";//輸出該塊左邊界對應水果序號 if(!k[i].isempty()){//非空就去掉第一個元素——左邊界右移 f[f[k[i].l].pre].next=f[k[i].l].next;//左邊界的上一水果的下一水果是左邊界的下一水果 f[f[k[i].l].next].pre=f[k[i].l].pre;//左邊界的下一水果的上一水果是左邊界的上水果 k[i].l=f[k[i].l].next;//塊的首水果變成水果的下一水果 }}int j=k[i].pre;//處理上一塊 if(k[j].isempty()){//如果上一塊空了，if(k[k[j].pre].d==k[k[j].next].d){//前后一樣，合并。//合并后塊到前塊 k[k[j].pre].r=k[k[j].next].r;//上一塊的右邊界改成下一塊的右邊界水果 k[k[j].pre].next=k[k[j].next].next;//前塊的后塊是后塊的后塊 k[k[k[j].next].next].pre=k[j].pre;//后塊的后塊的前塊是前塊 }else{//前后不一樣，續接上 k[k[j].pre].next=k[j].next;//前一個的下一個是自己下一個 k[k[j].next].pre=k[j].pre;//下一個的前一個是自己上一個 }}//view(i);}cout<<endl;//view();} return 0;
}

思路

• 模擬按塊取水果，并動態合并空塊
• 雙層雙向鏈表。水果塊和各水果
• 遍歷所有塊，并輸出每塊首水果。某塊被取空，如果前后塊一樣就合并，否則續接
• 每個水果會被處理1次(O(n))，每個果籃會被處理1次(O(n)),能處理n=2e5的規模。

小結

鏈表還是很有趣，多操作，熟能生巧。
都在處理序號，不管塊雙向鏈表和水果雙向鏈表。塊的首個水果和尾水果跟水果的序號統一。