낙 곡 [P1440] m 구간 내 최소 값 구하 기 (단조 대기 열)
11415 단어 데이터 구조 - 단조 대기 열
https://www.luogu.org/problem/P144
제목
n n n 의 길 이 를 가 진 서열 a a a 를 드 리 겠 습 니 다. a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i]] 이전의 m m 개수 중 가장 작은 값 인 [i - m, i - 1] [i - m, i - 1] [i - m, i - 1] [i - m, i - 1] [i - 1], i - 1] a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i]] a [i] a [i]] a [i] a [i]] a [i]] a [i] 값.
분석 하 다.
길이 m m 의 창 을 단조 로 운 대기 열 로 유지 하면 됩 니 다.읽 기 마 운 트 를 사용 하 세 요. cin 을 사용 하지 마 세 요. 그렇지 않 으 면 시간 을 초과 할 수 있 습 니 다.
코드
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x7f7f7f7f
#define MAXN 2000005
#define N 200005
#define P 2
//#define MOD 99991
#define MOD(a, b) a >= b ? a % b + b : a
typedef long long ll;
namespace fastIO {
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin),
// p1 == p2) ? EOF : *p1++) char buf[(1 << 22)], *p1 = buf, *p2 = buf;
inline int read() {
char c = getchar();
int x = 0, f = 1;
while (c < '0' || c > '9') {
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
x = x * 10 + c - '0', c = getchar();
return x * f;
}
} // namespace fastIO
using namespace fastIO;
using namespace std;
int n, m, t1, t2, a[MAXN], q[MAXN];
int main() {
cin >> n >> m;
//cin >> a[1];
//cout << 0 << endl;
for (int i = 1; i <= n; i++) {
a[i] = read();
if (i == 1) {
printf("0
");
q[++t2] = i;
t1++;
continue;
}
printf("%d
", a[q[t1]]);
while (t1 <= t2 && a[i] < a[q[t2]]) {
t2--;
}
q[++t2] = i;
//cout << q[t2] << " " << q[t1] << endl;
while (q[t2] - q[t1] + 1 > m) {
t1++;
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【 HDU 3401 】 Trade - 단조 로 운 대기 열 최적화 DP즉, dp [i] [j] ≥ dp [i - 1] [j] 이기 때문에 k 가 같은 상황 에서 dp [x] [k] 가 x 에서 최대 치 를 취 할 때 가장 크기 때문에 x 는 항상 i - w - 1 이 고 복잡 도 는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.