POJ 3776 Passing the Message
사고: 먼저 예비 처 리 를 진행 합 니 다. lf [i] 는 모든 수의 왼쪽 이 그것 보다 큰 첫 번 째 수의 아래 표 시 를 1 로 추가 합 니 다. rn [i] 은 모든 수의 왼쪽 이 그것 보다 큰 첫 번 째 수의 아래 표 시 를 1 로 줄 입 니 다.하나의 수 i 의 왼쪽 구간 의 최대 값 인 lf [j] 는 lf [i] 와 같 기 때문에 찾 을 때 하나의 수의 lf [j] = lf [i] 만 찾 으 면 이 수 는 가장 큰 수 이 고 오른쪽 구간 은 같 습 니 다.
코드:
#include <iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
#include<vector>
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-8
#define pi acos(-1.0)
using namespace std;
const int maxn=50000+10;
int lf[maxn],rn[maxn],num[maxn];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t,n,tcase=0;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
tcase++;
for(int i=1;i<=n;++i)
scanf("%d",&num[i]);
num[n+1]=num[0]=inf;
lf[0]=1;
rn[n+1]=n;
int p;
for(int i=1;i<=n;++i)
{
p=i;
lf[i]=i;
while(num[i]>num[p-1])
{
lf[i]=lf[p-1];
p=lf[p-1];
}
}
for(int i=n;i>=1;--i)
{
p=i;
rn[i]=i;
while(num[i]>num[p+1])
{
rn[i]=rn[p+1];
p=rn[p+1];
}
}
int ul,ur,pl,pr;
printf("Case %d:
",tcase);
for(int i=1;i<=n;++i)
{
ul=i-1;
ur=i+1;
pl=pr=0;
if(lf[i]!=i&&i-1!=0)
{
pl=ul;
while(lf[ul]!=lf[i])
{
if(ul==lf[ul])
ul--;
else
ul=lf[ul]-1;
pl=ul;
}
}
if(rn[i]!=i&&i!=n)
{
pr=ur;
while(rn[ur]!=rn[i])
{
if(ur==rn[ur])
ur++;
else
ur=rn[ur]+1;
pr=ur;
}
}
printf("%d %d
",pl,pr);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.