NC24097. [USACO 2017 Ope G]Modern Art 2
描述
Having become bored with standard 2-dimensional artwork (and also frustrated at others copying her work), the great bovine artist Picowso has decided to switch to a more minimalist, 1-dimensional style.
Although, her paintings can now be described by a 1-dimensional array of colors of length N (1≤N≤100,000), her painting style remains unchanged: she starts with a blank canvas and layers upon it a sequence of "rectangles" of paint, which in this 1-dimensional case are simply intervals. She uses each of the colors 1…N exactly once, although just as before, some colors might end up being completely covered up by the end.
To Picowso's great dismay, her competitor Moonet seems to have figured out how to copy even these 1-dimensional paintings, using a similar strategy to the preceding problem: Moonet will paint a set of disjoint intervals, wait for them to dry, then paint another set of disjoint intervals, and so on. Moonet can only paint at most one interval of each color over the entire process. Please compute
the number of such rounds needed for Moonet to copy a given 1-dimensional Picowso painting.
输入描述
The first line of input contains N, and the next N lines contain an integer in the range 0…N indicating the color of each cell in the 1-dimensional painting (0 for a blank cell).
输出描述
Please output the minimum number of rounds needed to copy this painting, or -1 if this could not have possibly been an authentic work of Picowso (i.e., if she could not have painted it using a layered sequence of intervals, one of each color).
示例1
输入:
7 0 1 4 5 1 3 3
输出:
2
说明:
In this example, the interval of color 1 must be painted in an earlier round than the intervals of colors 4 and 5, so at least two rounds are needed.C(clang11) 解法, 执行用时: 26ms, 内存消耗: 1608K, 提交时间: 2020-11-07 13:13:51
#include<stdlib.h>
#include<stdio.h>
struct color
{
int left;
int right;
};
int cmp(const void *a,const void *b)
{
return (*(struct color *)a).left-(*(struct color *)b).left;
}
struct color a[1000000];
struct color b[1000000];
nb;
int right[1000000];
int m,max;
int main()
{
int n;
scanf("%d",&n);
int i,j,k;
for(i=1;i<=n;i++)
{
scanf("%d",&k);
if(a[k].left==0)
a[k].left=a[k].right=i;
else
{
b[nb].left=a[k].right;
a[k].right=i;
b[nb].right=a[k].right;
nb++;
}
}
qsort(b,nb,8,cmp);
for(i=1;i<nb;i++)
if(b[i].right>b[i-1].right&&b[i].left<b[i-1].right)
{
printf("-1");
return 0;
}
qsort(a+1,n,8,cmp);
for(i=1;i<=n;i++)
{
if(a[i].left==0)
continue;
while(m>0&&a[i].left>right[m-1])
m--;
right[m]=a[i].right;
m++;
if(m>max)
max=m;
}
printf("%d",max);
}
C++(clang++11) 解法, 执行用时: 14ms, 内存消耗: 1732K, 提交时间: 2020-11-10 08:03:06
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,tp;
int a[N],mx[N],ix[N],d[N],stk[N];
inline void en(){puts("-1");exit(0);}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<=n;i++)
{
mx[a[i]]=i;
if(!ix[a[i]]) ix[a[i]]=i;
}
int ans=0;
for (int i=1;i<=n;i++)
{
if(a[i]==0)
{
if(tp) en();
continue;
}
if(ix[a[i]]==i)
{
if(tp&&mx[a[i]]>mx[stk[tp]]) en();
stk[++tp]=a[i];
ans=max(ans,tp);
}
if(mx[a[i]]==i) tp--;
}
printf("%d\n",ans);
return 0;
}