AGC029C Lexicographic constraints

题意

给定\(n\)个字符串长度\(a_i\)，求最少用多少个字符，才能构造出按字典序比较\(s1<s2<?<sn\)。
\(1 \leq N \leq 2 \times 10^5,1 \leq a_i \leq 10^9\)

思路

可以把字符串看为某个进制的数，如果说\(a_{i+1}>a_i\)直接补\(0\)即可，否则就找到第一个比他长度小的，若长度不够就补\(0\)，再\(+1\),看看到最后会不会爆尾数。\(1\)个字母的可以特判掉，发现剩下的其实可以用\(map\)维护

显然，有可二分性，二分答案即可。

#include <bits/stdc++.h>
using namespace std;
const int N=200005;
int n,a[N],ans,f=0;
map <int,int> mp;
bool check(int x){
    mp.clear();
    for (int i=2;i<=n;i++)
        if (a[i-1]>=a[i]){
            while (!mp.empty()){
                int t=mp.rbegin()->first;
                if (t>a[i]) mp.erase(t); 
                else break;
            }
            int j=a[i];
            while (mp[j]+1==x) mp.erase(j),j--;
            if (j==0) return false;
            mp[j]++;
        }
    return true;
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        if (a[i]<=a[i-1]) f=1;
    }
    if (!f) {puts("1");return 0;}
    int l=2,r=n;
    while (l<=r){
        int mid=(l+r)>>1;
        if (check(mid)){
            ans=mid;
            r=mid-1;
        }else l=mid+1;
    }
    printf("%d\n",ans);
}

AGC029C Lexicographic constraints

原文：https://www.cnblogs.com/flyfeather6/p/11760490.html