AtCoder Grand Contest 029C - Lexicographic constraints
题目大意
- 给出一个长为
N
N
N的序列
A
A
A，最小化能构造
N
N
N个字符串满足严格字典序升序且第
i
i
i个字符串的长度为
A
i
A_i
Ai的字符集大小。
-
N
≤
2
∗
1
0
5
N≤2*10^5
N≤2∗105
-
A
i
≤
1
∗
1
0
9
A_i≤1*10^9
Ai≤1∗109
题解
- 最早想的是从左往右直接贪心尽可能小地构造，但是会发现有些时候不能确定怎样才最优。
- 比如当前
A
i
=
A
i
+
1
=
3
A_i=A_{i+1}=3
Ai=Ai+1=3，构造到当前的串为“bac”，为了使长度不变且字典序变大，我们并不知道应该加一个字符’d’，变成“bad”，还是直接进位变成“bba”，
- 那可能会问，变成"bba"不是显然更优吗，其实不一定，万一后面有很多需要进位，进到最后不够了还是需要加’d’，而前面一段的进位是没有‘d’的，也就是说字符集的大小随着构造的过程才增大，到了后面字符集增大后，前面的构造就不是最优的了。
- 于是想到先二分出一个答案，然后在确定字符集大小的基础上构造，
- 如果
A
i
+
1
>
A
i
A_{i+1}>A_i
Ai+1>Ai，那么直接在后面补上若干个’a’（最小字符），
- 否则需要先把多出来的部分去掉，再进行进位操作，
- 如果进到首位了，那就说明字符集大小不够。
- 但发现
A
i
A_i
Ai特别大，所以不能一位一位的存，需要连续一段一段的存，相当于是一个栈，这样时间复杂度就可以保证了。
- 同时要注意的是，可能会有连续进位的情况，要记得循环不断进位，
- 还要注意栈中可能存在已经被清空的元素，记得删去。
代码
#include<cstdio>
#include<cstring>
using namespace std;
#define N 200010
int a[N];
struct {
int x, s;
}st[N];
int main() {
int n, i;
scanf("%d", &n);
for(i = 1; i <= n; i++) scanf("%d", &a[i]);
int l = 1, r = n, ans;
while(l <= r) {
int mid = (l + r) / 2;
int s = 0, t = 0, ok = 1;
for(i = 1; i <= n; i++) {
if(a[i] > s) {
st[++t].x = 1, st[t].s = a[i] - s;
s = a[i];
}
else {
int p = 0;
while(s > a[i]) {
if(s - st[t].s > a[i]) s -= st[t].s, st[t].s--, t--;
else {
st[t].s -= s - a[i];
s = a[i];
}
}
while(st[t].s == 0) t--;
p = st[t].x;
int j = t;
while(st[j].x == mid && j) j--;
if(j == 0) {
ok = 0;
break;
}
if(st[j].s == 1) {
j = t;
while(st[j].x == mid && j) {
st[j].x = 1;
j--;
}
st[j].x++;
}
else {
j = t, t++;
while(st[j].x == mid && j) {
st[j + 1] = st[j];
st[j + 1].x = 1;
j--;
}
st[j + 1].x = st[j].x + 1, st[j + 1].s = 1;
st[j].s--;
}
}
}
if(ok) ans = mid, r = mid - 1; else l = mid + 1;
}
printf("%d", ans);
return 0;
}