hdoj 최 단 구간 판 여러분 이 찾 아 오 세 요 2158 (폭 력 시 뮬 레이 션)
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 844 Accepted Submission(s): 297
Problem Description
하나의 서열 을 정 하고 N 개의 정수 가 있 으 며 수치 범 위 는 [0, N) 입 니 다.
주어진 Q 개의 정 수 를 물 어 볼 때마다 반복 값 이 나타 날 수 있 는 M 개의 질문 이 있 습 니 다.
이 Q 개의 정수 수 치 를 포함 하 는 최 단 구간 을 찾 아야 한다.
찾 아 낼 수 있 겠 소?
Input
첫 번 째 줄 에는 두 개의 정수 N, M 이 있 습 니 다. (N < 100000, M < 1000) 다음 줄 에는 N 개의 정수 가 있 습 니 다. 그리고 M 개의 질문 이 있 습 니 다. 첫 번 째 줄 마다 정수 Q (Q < 100) 가 있 고 두 번 째 줄 은 Q 개의 정 수 를 따 릅 니 다. N, M 이 동시에 0 일 때 입력 이 끝 납 니 다.
Output
최 단 구간 의 길 이 를 출력 해 주 십시오.
Sample Input
5 2
1 2 2 3 1
3
1 2 3
3
1 1 3
0 0
Sample Output
3
2
Hint
第二个查询，找到的区间是[4,5]
//大神写的，，，表示还没看懂。。。找个时间再静心推一下。
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define INF 0x3f3f3f
#define N 100010
using namespace std;
int s[N];
int num[N];
int mark[N];
int pos[N];
int main()
{
int n,m,q,a;
while(scanf("%d%d",&n,&m),n|m)
{
memset(mark,0,sizeof(mark));
memset(pos,-1,sizeof(pos));
for(int i=0;i<n;i++)
{
scanf("%d",&s[i]);
if(pos[s[i]]==-1)
pos[s[i]]=i;
}
s[n]=n;
for(int i=1;i<=m;i++)
{
scanf("%d",&q);
int l=n,r=-1,mm=INF;
for(int j=0;j<q;j++)
{
scanf("%d",&a);
num[a]=0;
mark[a]=i;
if(pos[a]>r)
r=pos[a];
if(pos[a]<l)
l=pos[a];
}
for(int j=l;j<=r;j++)
num[s[j]]++;
mm=r-l+1;
while(r<n)
{
num[s[l]]--;
if(!num[s[l]])
{
while(++r<n&&s[r]!=s[l])
num[s[r]]++;
num[s[r]]=1;
}
while(++l<=r&&mark[s[l]]!=i);
if(r<n&&mm>r-l+1)
mm=r-l+1;
}
printf("%d
",mm);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
