简答题
偏难
#7357
现代艺术 在对二维艺术作品感到厌烦之后,伟大的艺术牛Picowso决定从事创作一项更为小众的艺术形式,一维画。 尽管目前她的画作可以用一个由颜色组成的长度为N(…
现代艺术
在对二维艺术作品感到厌烦之后,伟大的艺术牛Picowso决定从事创作一项更为小众的艺术形式,一维画。
尽管目前她的画作可以用一个由颜色组成的长度为N(1~100000)的数组表示,但她的创作风格依然保持不变:从一张空白的矩形画布上,不断地画上一些矩形,在一维的情况下,这些矩形就只是一个区间。她用N种颜色,颜色编号为1~N进行创作,每种颜色只使用一次,之后使用的颜色可以完全的覆盖之前在相同位置上的颜色。
令Picowso感到十分沮丧的是,她的竞争对手Moonet似乎弄明白了如何复制她的这些一维画作,Moonet会画一些不相交的间隔,等待这些颜色晾干,然后再画另外的一些间隔,直到画完。Moonet每次每种颜色最多只能画一个间隔,但是他可以一次画不同颜色不相交的多个间隔,只要这些间隔没有重叠部分。之后Moonet再进行下一轮绘制。请计算Moonet为了复制一幅画需要画几个回合。
时间限制:10000
内存限制:65536
输入
第一行是一个整数N,之后N行包含了N个整数,范围0到N表示纸带每个格点的颜色,0表示没有涂色。
输出
输出一行,需要复制这幅画作的最少回合数,如果这幅画不可能是Picowso的画作输出-1(比如说这幅画不可能是通过一次在一条上画一层的方法进行创作的)
样例输入
7 0 1 4 5 1 3 3
样例输出
2
提示
在这个样例中,第一轮涂成0111133,第二轮涂成0145133,所以共需两轮。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int end_pos[N], a[N];
int n, result, flag = 1;
char v[N];
stack<int> s;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i += 1) {
scanf("%d", &a[i]);
end_pos[a[i]] = i; // 记录每个颜色的终点位置
}
v[0] = 1; // 初始化 将0视为覆盖整个画布的第一种颜色
end_pos[0] = n + 1;
s.push(0);
for (int i = 1; i <= n && flag; i++) {
if (s.top() != a[i]) {
if (v[a[i]])
flag = 0; // 颜色被使用过 标记非法
s.push(a[i]); // 加入新的颜色
}
v[a[i]] = 1; // 标记该颜色被使用过
result = max(result, (int)s.size());
if (i == end_pos[a[i]]) {
s.pop(); // 该颜色最后一次被使用 弹出改颜色
}
}
if (!flag)
cout << -1;
else
cout << result - 1;
return 0;
}</pre>
这道题暂未补解析。