单调队列如果用２分貌似使时间复杂度增加到O(nlogn) 如果不用二分的单调队列 均摊时间确是O(n) 但是这题用２分优化的版本可以过 谁知道可以用２分优化 均摊时间还是O(n)的算法 可以交流一下
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
#define N 1000005
class Elem
{
public:
int val;
int index;
Elem(int val, int index)
{
this->val=val;
this->index=index;
}
Elem() {}
static bool lesser(const Elem& x, const Elem&y)
{
return x.val<y.val;
}
static bool greater(const Elem& x, const Elem&y)
{
return x.val>y.val;
}
};
template <class T>
class Queue
{
public:
T* array, *head, *tail;
bool (*compareT)(const T& x, const T&y);
Queue(T* array, bool (*compareT)(const T& x, const T&y))
{
this->array=array;
head=tail=array;
this->compareT=compareT;
}
void init(T* array, bool (*compareT)(const T& x, const T&y))
{
this->array=array;
head=tail=array;
this->compareT=compareT;
}
void push(const Elem& elem)
{
tail=lower_bound(head,tail,elem,compareT);
*tail=elem; tail++;
}
void pop()
{
head++;
}
};
void output(const Queue<Elem>& q)
{
Elem* iter;
for(iter=q.head;iter!=q.tail;iter++)
{
printf("[%d,%d] ",iter->val,iter->index);
}
printf("\n");
}
int d[N];
Elem elems[N];
int n,k;
int main()
{
freopen("d.in","r",stdin);
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) scanf("%d",&d[i]);
Queue<Elem> q(elems, Elem::lesser);
for(int i=0;i<n;i++)
{
Elem e(d[i],i);
q.push(e);
if(i-q.head->index>=k) q.pop();
if(i>=k-1) printf("%d ",q.head->val);
//output(q);
}
printf("\n");
q.init(elems, Elem::greater);
for(int i=0;i<n;i++)
{
Elem e(d[i],i);
q.push(e);
if(i-q.head->index>=k) q.pop();
if(i>=k-1) printf("%d ",q.head->val);
//output(q);
}
printf("\n");
return 0;
}