A38147. 现代艺术在对二维艺术作品感到厌烦之后，伟大的艺术牛Picowso决定从事创作一项更为小众的艺术形式，一维画。尽管目前她的画作可以用一个由颜色组成的长度为N(1~100000)的数组表示，但她的创作风格依然保持不变：从一张空白的矩形画布上，不断地画上一些矩形，在一维的情况下，这些矩形就只是一个区间。她用N种颜色，颜色编号为1~N进行创作，每种颜色只使用一次，之后使用的颜色可以完全的覆盖之前在相同位…
填空题
困难
知识点
题目描述
现代艺术
在对二维艺术作品感到厌烦之后，伟大的艺术牛Picowso决定从事创作一项更为小众的艺术形式，一维画。
尽管目前她的画作可以用一个由颜色组成的长度为N(1~100000)的数组表示，但她的创作风格依然保持不变：从一张空白的矩形画布上，不断地画上一些矩形，在一维的情况下，这些矩形就只是一个区间。她用N种颜色，颜色编号为1~N进行创作，每种颜色只使用一次，之后使用的颜色可以完全的覆盖之前在相同位置上的颜色。
令Picowso感到十分沮丧的是，她的竞争对手Moonet似乎弄明白了如何复制她的这些一维画作，Moonet会画一些不相交的间隔，等待这些颜色晾干，然后再画另外的一些间隔，直到画完。Moonet每次每种颜色最多只能画一个间隔，但是他可以一次画不同颜色不相交的多个间隔，只要这些间隔没有重叠部分。之后Moonet再进行下一轮绘制。请计算Moonet为了复制一幅画需要画几个回合。
输入
第一行是一个整数N，之后N行包含了N个整数，范围0到N表示纸带每个格点的颜色，0表示没有涂色。
输出
输出一行，需要复制这幅画作的最少回合数，如果这幅画不可能是Picowso的画作输出-1（比如说这幅画不可能是通过一次在一条上画一层的方法进行创作的）
样例输入
7
0
1
4
5
1
3
3
样例输出
2
提示
在这个样例中，第一轮涂成0111133，第二轮涂成0145133，所以共需两轮。
参考答案
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
int end_pos[MAXN], canvas[MAXN];
int N, result, flag = 1;
/* flag = 1 means legal */
char Visit[MAXN];
stack<int> sta;
int main() {
scanf("%d", &N);
for (int i = 1;i <= N;i += 1) {
scanf("%d", canvas + i);
// record the end point of every interval
end_pos[canvas[i]] = i;
}
// view 0 as the first color that covers the entire canvas
Visit[0] = 1;
end_pos[0] = N + 1;
sta.push(0);
// loop through the canvas
for (int i = 1;i <= N && flag;i += 1) {
if(sta.top() != canvas[i]) {
// an illegal painting
if(Visit[canvas[i]])
flag = 0;
sta.push(canvas[i]);
}
Visit[canvas[i]] = 1;
result = max(result, (int)sta.size());
// an interval ends
if(i == end_pos[canvas[i]])
sta.pop();
}
// result-1 because the extra 0
printf("%d\n", (flag ? result - 1: -1));
return 0;
}
上一题
下一题