로곡 P2032 스캔(단일 대기열)

3150 단어

전송문


문제풀이의 방향


간단한 틀이야.
원래는 문제풀이를 쓰고 싶지 않았는데, 이번 단조로운 대열은 정말 짧게 썼구나!QAQ
템플릿 보기:단일 대기열

AC 코드

 1 #include
 2 #include
 3 #include
 4 using namespace std;
 5 int n,k,a[1000005];
 6 deque<int> q;
 7 int main()
 8 {
 9     cin>>n>>k;
10     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
11     for(int i=1;i<=n;i++){
12         if(q.empty()) q.push_back(i);
13         else{
14             if(q.front()+k<=i) q.pop_front();
15             while(!q.empty()&&a[q.back()]<=a[i]) q.pop_back();
16             q.push_back(i);
17         }
18         if(i>=k) printf("%d
",a[q.front()]); 19 } 20 return 0; 21 }

 

 

좋은 웹페이지 즐겨찾기