BZOJ3152[Ctsc2013]组合子逻辑—

BZOJ3152[Ctsc2013]组合子逻辑——堆+贪心

阅读量：6917 次

发布时间：2019-06-27

本文共 1182 字，大约阅读时间需要 3 分钟。

题目链接：

题目大意：

一开始有一个括号包含[1,n]，你需要加一些括号，使得每个括号(包括一开始的)所包含的元素个数要<=这个括号左端点那个数的大小，当一个括号包含另一个括号时，里面那个括号内所有数整体被看作是一个元素。

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;priority_queue
                
                 q;int T;int n;int a[2000010];int now;int ans;int flag;int main(){ scanf("%d",&T); while(T--) { while(!q.empty()) { q.pop(); } ans=0; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } if(n==1) { printf("0\n"); continue; } now=a[1]-1; ans++; flag=0; if(now==0) { printf("-1\n"); continue; } for(int i=2;i<=n;i++) { if(now==0) { now=q.top()-1; q.pop(); if(now==0) { flag=1; break; } ans++; } now--; q.push(a[i]); } if(flag==1) { printf("-1\n"); continue; } printf("%d\n",ans); }}