NC 51001 Sliding Windowスライドウィンドウ最大最小値問題スタック最適化

リンク:https://ac.nowcoder.com/acm/problem/51001出典:牛客網
タイトルはAn array of size n≦106 is given to you.There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example: The array is [1 3 -1 -3 5 3 6 7], and k is 3. Window position Minimum value Maximum value [1 3 -1] -3 5 3 6 7 -1 3 1 [3 -1 -3] 5 3 6 7 -3 3 1 3 [-1 -3 5] 3 6 7 -3 5 1 3 -1 [-3 5 3] 6 7 -3 5 1 3 -1 -3 [5 3 6] 7 3 6 1 3 -1 -3 5 [3 6 7] 3 7 Your task is to determine the maximum and minimum values in the sliding window at each position.
説明を入力:
The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.
出力の説明:
There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.
例1入力コピー
8 3 1 3 -1 -3 5 3 6 7
出力レプリケーション
-1 -3 -3 -3 3 3 3 3 5 5 6 7
クラシックな問題、スライドウィンドウの最値の問題、

スタック最適化O(nl o g n)O(nlogn)O(nlogn)

構造体は、数字の下付き文字と数字自体

を保存する.

struct Node {
     
	int id, val; //    
	bool operator < (const Node& no) const {
     
		return val < no.val;
	}
	bool operator > (const Node& no) const {
     
		return val > no.val;
	}
} ;

ウィンドウ(大きなスタック、小さなスタック)

をシミュレートするために2つのスタックを使用します.

std::priority_queue<Node> q1; //   
std::priority_queue<Node, vector<Node>, greater<Node> > q2;

初期化ウィンドウにはM−1 M−1 M−1要素

がある.

for(int i=1; i<m; i++) //       m-1   
   	q1.push({
     i, a[i]}), q2.push({
     i, a[i]});

は、1つの要素a[i]a[i]a[i]を加えるたびに、スタック内をウィンドウ区間[i−M+1,i][i−M+1,i][i−M+1,i]内のポップアップ

にしない

for(int i=m; i<=n; i++) {
     
	q2.push({
     i, a[i]}); //        
	while(tb.id <= i-m) q2.pop(); //                
	printf("%d%c", tb.val, i==n?'
':' '); //          
}

完全なコードは次のとおりです.

#define debug
#ifdef debug
#include 
#include "/home/majiao/mb.h"
#endif

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define MAXN ((int)1e6+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \
do { \
	cout << "\033[31;1m " << #x << " -> "; \
	err(x); \
} while (0)

void err() {
      cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) {
      cout << a << ' '; err(x...); }
#endif

#ifndef debug
namespace FIO {
     
	template <typename T>
	void read(T& x) {
     
		int f = 1; x = 0;
		char ch = getchar();

		while (ch < '0' || ch > '9') 
			{
      if (ch == '-') f = -1; ch = getchar(); }
		while (ch >= '0' && ch <= '9') 
			{
      x = x * 10 + ch - '0'; ch = getchar(); }
		x *= f;
	}
};
using namespace FIO;
#endif

#define ta (q1.top())
#define tb (q2.top())

int n, m, Q, K, a[MAXN];
struct Node {
     
	int id, val;
	bool operator < (const Node& no) const {
     
		return val < no.val;
	}
	bool operator > (const Node& no) const {
     
		return val > no.val;
	}
} ;

std::priority_queue<Node> q1; //   
std::priority_queue<Node, vector<Node>, greater<Node> > q2;

int main() {
     
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	read(n), read(m);
	for(int i=1; i<=n; i++) read(a[i]);
	for(int i=1; i<m; i++) //       m-1   
		q1.push({
     i, a[i]}), q2.push({
     i, a[i]});

	for(int i=m; i<=n; i++) {
     
		q2.push({
     i, a[i]}); //        
		while(tb.id <= i-m) q2.pop(); //                
		printf("%d%c", tb.val, i==n?'
':' '); //          
	}
	for(int i=m; i<=n; i++) {
     
		q1.push({
     i, a[i]});
		while(ta.id <= i-m) q1.pop();
		printf("%d%c", ta.val, i==n?'
':' ');
	}





#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf  
",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}