【AtCoder Grand Contest 029 C】Lexicographic constraints | Mrsrz's blog

二分答案，贪心，栈。

题目大意：

给定一个大小为 $n$ 的字符串数组 $s_1,s_2,\ldots,s_n$。

已知第 $i$ 个字符串的长度为 $A_i$。

求字符集大小至少为多少，使得存在满足条件的字符串数组，其字典序严格递增。

题解：

答案显然满足可二分性，考虑二分答案并且判断字符集为 $c$ 是否可行。

我们从小到大确定每个字符串，每次令其为比上一个字符串字典序大的，字典序最小的字符串。这样保证最后一个是最小的。

若 $A_i\lt A_j$，则在 $s_i$ 后补上 $A_j-A_i$ 个最小的字符即可。

若 $A_i\geq A_j$，则取 $s_i$ 的长度为 $A_j$ 的前缀，并令最后一个字符加一即可。若超过 $c$ 则往前进位，以此类推。

我们用栈记录所有不是最小的字符的位置以及其字符。

若 $A_i\lt A_j$，则栈中无变化。

若 $A_i\geq A_j$，则弹出栈中位置超过 $A_j$ 的元素，然后若不存在 $A_j$，则插入倒数第二小的字符，否则令其加一。若产生进位，则删掉这个位置，往前考虑，直到进位结束或发现无法进位。若无法进位则这个 $c$ 不可行。

如果 $n$ 个串都成功确定，则 $c$ 可行。

每次只会删除若干个栈中元素，插入最多 $1$ 个元素，修改最多 $1$ 个原有元素。每个栈中元素只会被删一次，因此时间复杂度 $O(n)$。

答案为 $1$ 的情况可以特判，不难发现当且仅当 $A_i$ 严格递增时，答案为 $1$。

时间复杂度 $O(n\log V)$。

Code：

#include<cstdio>
const int N=2e5+6;
int n,A[N];
int a[N],b[N],top;
bool check(int c){
    top=0;
    for(int i=2;i<=n;++i)
    if(A[i]<=A[i-1]){
        int pos=A[i];
        while(top&&a[top]>pos)--top;
        if(!top||a[top]!=pos)a[++top]=pos,b[top]=1;else{
            while(top&&a[top]==pos&&b[top]==c-1)--top,--pos;
            if(!pos)return 0;
            if(top&&a[top]==pos)++b[top];else a[++top]=pos,b[top]=1;
        }
    }
    return 1;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",A+i);
    bool ok=1;
    for(int i=1;i<=n;++i)if(A[i]<=A[i-1])ok=0;
    if(ok){puts("1");return 0;}
    int l=2,r=1e9,ans=1e9;
    while(l<=r){
        const int mid=l+r>>1;
        if(check(mid))r=(ans=mid)-1;else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}