[데이터 구조] CODE [VS] 4373 창 (양 끝 대기 열 슬라이딩 창)

클릭 하여 창 가 져 오기
쓰레기 문제, 내 청춘 망 쳐.
양 끝 대기 열의 응용 문제, 미끄럼 창의 템 플 릿 문제?왜 나 말고 다 시 뮬 레이 션 을 해? 나 만 STL 로??
읽 으 면서 조작 합 니 다. 최대 최소 분리 작업 입 니 다. 대기 열 에 이 숫자 가 저 장 된 아래 표 시 된 시효 가 지 났 습 니 다. 전단 에서 최소 값 을 꺼 낼 때 가장 작은 것 을 팀 의 머리 에 놓 습 니 다. 만약 에 새로운 요소 가 팀 의 꼬리 보다 작 으 면 꼬리 에 팝 업 됩 니 다. 최대 값 을 꺼 낼 필요 가 없 을 때 가장 큰 것 을 팀 의 머리 에 놓 습 니 다. 만약 에 새로운 요소 가 팀 의 꼬리 보다 크 면 꼬리 에 팝 업 됩 니 다.당신 은 * 2 마지막 출력 이 필요 없 기 때문에 숫자 사이 에 빈 칸 을 추가 하고 줄 을 바 꾸 는 것 을 잊 지 마 세 요.
코드 는 다음 과 같 습 니 다:

#include 
#include 
#include 
#include 
#include 
#include 
#define maxn 1000006

using namespace std;

int n,k;
int num[maxn];
int maxx[maxn],minn[maxn];

deque<int >q1;
deque<int >q2;

inline void rd(int &x)
{
    scanf("%d",&x);
}

inline void work()
{
    for(int i = 1;i <= n;i++)
    {
        rd(num[i]);
        while(!q1.empty() && num[q1.back()] >= num[i]) q1.pop_back();
        q1.push_back(i);
        if(i >= k)
        {
            while(!q1.empty() && q1.front() <= (i-k)) q1.pop_front();
            minn[i] = num[q1.front()];
        }
        while(!q2.empty() && num[q2.back()] <= num[i]) q2.pop_back();
        q2.push_back(i);
        if(i >= k)
        {
            while(!q2.empty() && q2.front() <= (i-k)) q2.pop_front();
            maxx[i] = num[q2.front()];
        }

    }   
    for(int i = k;i <= n;i++) printf("%d ",minn[i]);puts("
");
    for(int i = k;i <= n;i++) printf("%d ",maxx[i]);puts("
");
}

int main()
{
    rd(n);rd(k);
    work();
return 0;
}

THE END
By Peacefuldoge
http://blog.csdn.net/loi_peacefuldog