POI2010 Blocks
N 개의 정수 a [1. N] 를 제시 하고 정수 k 를 제시 합 니 다. 이 제 는 다음 과 같은 작업 을 할 수 있 습 니 다. k 이상 의 정수 a [i] 를 선택 할 때마다 a [i] 를 1 로 줄 이 고 a [i - 1] 또는 a [i + 1] 중 하 나 를 추가 합 니 다.일정한 횟수 의 조작 을 거 친 후에 최대 얼마나 긴 연속 서브 시퀀스 를 선택 할 수 있 는 지 물 어보 면 이 서브 시퀀스 의 모든 수 는 k 보다 작 지 않 습 니 다.
총 M 번 의 질문 을 드 립 니 다. 매번 질문 할 때마다 K 가 다 르 기 때문에 각각 대답 해 야 합 니 다.
입력
첫 줄 의 두 개의 정수 N (N < = 1000000) 과 M (M < = 50).
두 번 째 줄 의 N 개 정 수 는 a [i] (a [i] < = 10 ^ 9) 를 나타 낸다.
세 번 째 줄 M 개의 정수, 세 번 째 정 수 는 i 번 째 문의 k (k < = 10 ^ 9) 를 나타 낸다.
출력
모두 한 줄 로 M 개의 정 수 를 출력 하고 i 번 째 수 는 i 번 째 질문 의 답 을 표시 합 니 다.
nlogn 은 그래도 생각 했 습 니 다. 각각 kd 에서 얻 은 접두사 와. 그리고 단조 로 운 스 택 으로 유지 하고 2 분 마다 그 접두사 와 같은 접 두 사 를 찾 습 니 다.
O (n) 의 방법 도 차이 가 많 지 않 습 니 다. 단조 로 운 스 택 (단조 로 운 감소) 을 유지 한 다음 에 모든 접두사 와 스 택 꼭대기 요소 가 현재 접두사 와 같 을 때 계속 팝 업 됩 니 다. 그러면 가장 좋 은 결 과 를 얻 을 수 있 습 니 다. (정확성 은 생각 합 니 다)
#include 1]]) stk[tot++]=i;
}
int ans=0;
for (int i=n;i>=1;--i) {
while (tot&&sum[i]>=sum[stk[tot-1]]) tot--;
ans=max(ans,i-stk[tot]);
}
printf("%d",ans);
}
int main() {
cin>>n>>m;
for (int i=1;i<=n;++i) scanf("%d",&num[i]);
for (int i=1;i<=m;++i) {
if (i!=1) printf(" ");
solve();
}
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
