codeforce452DIV2——E. Segments Removal

题目

Vasya has an array of integers of length n.

Vasya performs the following operations on the array: on each step he finds the longest segment of consecutive equal integers (the leftmost, if there are several such segments) and removes it. For example, if Vasya's array is [13, 13, 7, 7, 7, 2, 2, 2], then after one operation it becomes [13, 13, 2, 2, 2].

Compute the number of operations Vasya should make until the array becomes empty, i.e. Vasya removes all elements from it.

分析

链表+优先队列

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <iostream>

 #include <queue>

 using namespace std;

 const int maxn=+;

 int a[maxn];

 int vis[maxn];

 struct Node{

     int len,id,val,l;

     bool operator <(const Node &rhs)const{

         return len<rhs.len||(len==rhs.len&&l>rhs.l);

     }

 }node[maxn];

 int n;

 int Next[maxn],Last[maxn];

 int main(){

     memset(vis,,sizeof(vis));

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         scanf("%d",&a[i]);

     }

    int cnt=,m=;

     for(int i=;i<=n;i++){

         cnt++;

         if(a[i]!=a[i+]){

             node[++m].len=cnt;

             node[m].id=m;

             node[m].val=a[i];

             node[m].l=i;

             cnt=;

         }

     }

     priority_queue<Node>q;

     //printf("%d",m);

     for(int i=;i<=m;i++){

         Next[i]=i+;

         Last[i]=i-;

         q.push(node[i]);

     }

     Next[m]=;Last[]=;

     int ans=;

     while(!q.empty()){

         while(!q.empty()&&vis[q.top().id])q.pop();

         if(!q.empty()){

         Node x=q.top();q.pop();

         //printf("%d :%d %d\n",x.id,Next[x.id],Last[x.id]);

         //printf("%d %d %d\n",x.id,x.len,x.val);

         ans++;

         Next[Last[x.id]]=Next[x.id];

         Last[Next[x.id]]=Last[x.id];

         if(Last[x.id]&&Next[x.id]&&node[Last[x.id]].val==node[Next[x.id]].val&&!vis[node[Last[x.id]].id]&&!vis[node[Next[x.id]].id]){

                 vis[node[Last[x.id]].id]=;

                 vis[node[Next[x.id]].id]=;

                 int l=node[Next[x.id]].l;

                 node[++m].val=node[Last[x.id]].val;

                 node[m].len=node[Last[x.id]].len+node[Next[x.id]].len;

                 node[m].id=m;

                 node[m].l=l;

                 Next[Last[Last[x.id]]]=m;

                 Last[Next[Next[x.id]]]=m;

                 Next[m]=Next[Next[x.id]];

                 Last[m]=Last[Last[x.id]];

                 q.push(node[m]);

         }

         }

     }

    printf("%d",ans);

 return ;

 }

巴特西

codeforce452DIV2——E. Segments Removal

最新文章

热门文章