欢迎hcak,再hack,估计就是思路问题了
贪心 $O(n^2) or O(nlogn)$
二分图染色就不说了, 题解都是
而且二分染色是到不了复杂度 nlogn 的
首先贪心, 总基调
能操作 b, 则一定不能操作a(判断 b 的优先级高于 a)
能操作 d, 则一定不能操作c (判断 d 的优先级高于 c)
- 首先判断 b 操作
- 再判断 a 操作
- 再判断 d 操作
- 最后判断 c 操作
那么问题来了如何判断能不能入栈呢?
首先 栈顶小于 x[i] 是肯定不能入的
再对于栈 a, 把 x[i] 放入, 那么在 x[i] 出栈之前比 x[i] 小的数不能入栈a
即保证 x[i] 出栈之前不存在 x[j] 无法放入任何一个栈
否者只能尝试将 x[i] 放入栈 b
再否则就失败了
设 f[x[i]] 表示 x[i] 出栈前最大的数
则 $f[x[i]] = max(f[x[i] - 1], x[i] - 1)$
若 x[i] - 1 出现的位置在 x[i] 之后 j 那么
$ f[x] = max(f[x], max(f[x[i + 1$ ~ $j - 1]], x[i + 1$ ~ $j - 1])) $
至此此题就做完了
感谢 Abosite hack
在弹S2之后不能直接压栈, 要判断S1当前是否能弹
感谢 aacc
强制延后栈B的弹栈时间(主要我判断能不能压栈要基于操作 3, 操作2、3的依赖性反着的,暂想不到更好的优化)
时间复杂度
复杂度上限在 x[i] 到 x[i] - 1 位置之间的数 的最大值这里
我们可以选择用任何一种数据结构维护区间最大值实现将 n 优化为 logn
所以这道题的n可以扩大为 1e6
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int a[1005], f[1005];
bool v[1005];
int main() {
string s, t; int n, k = 1; cin >> n; stack<int> x, y; x.push(1e9); y.push(1e9);
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = n, j = a[i] - 1; i; v[a[i]] = 1, j = a[--i] - 1) {
if (!v[j]) f[j + 1] = 0;
else {
bool g = 0; f[j + 1] = f[j];
for (int k = i + 1; a[k] != j; ++k) f[j + 1] = max(f[j + 1], max(f[a[k]], a[k]));
}
}
for (int i = 1, c = a[1]; i <= n; c = a[++i]) {
while (x.top() == k) {
s += t, t = "";
++k, s += 'b', x.pop();
}
if (x.top() > c && f[c] < y.top()) s += 'a', x.push(c);
else if (y.top() == k) t += 'd', ++k, y.pop(), --i;
else {
if (y.top() > c) s += t, s += 'c', y.push(c), t = "";
else { s = ""; break; }
}
}
if (s.empty()) return cout << 0, 0;
while (x.top() == k || y.top() == k)
if (x.top() == k) ++k, s += 'b', x.pop();
else ++k, s += 'd', y.pop();
for (auto c : s) cout << c << ' ';
return 0;
}
hack数据:
8
8 2 4 1 5 3 7 6
正解:a a c a b b a a b d b a a b b b
你的解:a a c a b b a a b d c b a b d b
感谢, 没考虑全, 改好了
已经申请加强数据了
居然可以贪心,那是不是能动归呢
9
1 7 3 6 2 4 8 5 9
a b a c a a b a d b c a b b b a d b
数据来自https://www.acwing.com/solution/content/23011/
感谢
暂时想到,强制延后栈B的弹栈时间(主要我判断能不能压栈要基于操作 3, 操作2、3的依赖性反着的,暂想不到更好的优化)