[BZOJ 3152]サブロジックの組合せ

テキストリンク:http://www.cnblogs.com/newera/p/9131045.html
Link:
BZOJ 3152トランスポートゲート
Solution:
喜ばしいことに、gyzが出した国語の問題は、30分も見なければならない.
 
タイトル:最小のカッコを使用してシーケンスを分割し、カッコ内のシーケンスごとに、左端の数を$num$とし、シーケンス内の要素の数を$cnt$とします.
保証するには、$num>=cnt$(カッコで囲まれた要素)です.最初はカッコに$[1,n]$が含まれていました.
 
最初はカッコに$[1,n]$が含まれていたので、
最初から欲張るだけで、拡張できる個数と現在の最大値を維持できます.
Note:注意$n=1$の特殊処理
Code:

#include 

using namespace std;

inline int read()
{
    char ch;int num,f=0;
    while(!isdigit(ch=getchar())) f|=(ch=='-');
    num=ch-'0';
    while(isdigit(ch=getchar())) num=num*10+ch-'0';
    return f?-num:num;
}

int T,n,x,dat[2000005];

int main()
{
    T=read();
    while(T--)
    {
        n=read();priority_queue<int> que;
        if(n==1){puts((read())?"0":"-1");continue;}
        for(int i=1;i<=n;i++) dat[i]=read();
        
        int k=dat[1]-1,res=1;
        for(int i=2;i<=n;i++)
        {
            if(k){k--;que.push(dat[i]);continue;}
            
            if(que.empty() || que.top()<2){res=-1;break;}
            res++;k=que.top()-2;que.pop();que.push(dat[i]);
        }
        printf("%d
",res);
    }
    return 0;
}

転載先:https://www.cnblogs.com/newera/p/9131045.html