CSP2021-J T4

· · 题解

题外话：今年题是不是有点简单啊。。。

这题作为 T4 感觉真的有点简单，我们用一个链表把一个个块连起来，每个块内再用一个链表维护块内有哪些位置的，然后按照题目模拟就行了，由于每个水果最多被删除一次，所以时间复杂度是 O(n) 的。

具体实现是这样的：

  1. 遍历每个块，删掉第一个水果，然后判断删掉后是否还有水果，如果还有跳过第 2 步
  2. 把它前面还没删掉的那个块和它后面的那个块连在一起，但在连上之前后面那个块也要把第一个水果删掉（因为题目说是同时删掉），再把自己删掉。
  3. 如果还有块的话，回到第 1 步

考场代码：

#include<stdio.h>
#include<ctype.h>
FILE *in=fopen("fruit.in","r"),*out=fopen("fruit.out","w");
namespace fasti{
    char buf[1<<15],*p1=buf,*p2=buf;
    #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<15,in),p1==p2)?EOF:*p1++)
    inline void read(int&x){
        char c=getc();
        for(;!isdigit(c);c=getc());
        for(x=0;isdigit(c);c=getc())x=(x<<1)+(x<<3)+(c^48);
    }
}
using fasti::read;
int nxt[200010];
struct{
    int nxt,b,e;
}list[200010];
int a[200001],n;
int main(){
    read(n);
    for(int i=1;i<=n;++i)read(a[i]);
    int head=0,tail=0;
    for(int i=1,j;i<=n;i=j){
        list[tail].b=list[tail].e=i;
        for(j=i+1;j<=n&&a[i]==a[j];++j)
            list[tail].e=nxt[j-1]=j;
        list[tail].nxt=tail+1,++tail;
    }
    for(;head!=tail;){
        int last=-1;
        for(int i=head;i!=tail;i=list[i].nxt){
            fprintf(out,"%d ",list[i].b),list[i].b=nxt[list[i].b];
            if(!list[i].b){
                if((~last)&&list[i].nxt!=tail){
                    fprintf(out,"%d ",list[i=list[i].nxt].b),list[i].b=nxt[list[i].b];
                    if(list[i].b)nxt[list[last].e]=list[i].b,list[last].e=list[i].e;
                    list[last].nxt=list[i].nxt;
                }
                else if(~last)list[last].nxt=tail;
                else head=list[i].nxt;
            }else last=i;
        }
        fputc('\n',out);
    }
    fclose(in);
    fclose(out);
    return 0;
}