鼠鼠再怎么优化也过不了这个单调队列
查看原帖
鼠鼠再怎么优化也过不了这个单调队列
1428433
kendas楼主2024/10/30 14:55

受不鸟了求调

#include <iostream>
#include <deque>
using namespace std;

const int N = 2000005;
int s[N], q[N] , tt = -1, hh;

int find(int x)
{
    int l = hh, r = tt;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(s[q[mid]] >= x) r = mid;
        else l = mid + 1;
    }
    return r;
}

int main()
{
    int n, m;cin>>n>>m;
    for(int i = 1; i <= n; i ++)cin>>s[i];
    for(int i = 1; i <= n; i ++)
    {
        if(i - m > q[hh]) hh ++;
        if(hh <= tt && s[q[tt]] >= s[i]) tt = find(s[i]) - 1;
        if( i >= 1 && q[hh])cout << s[q[hh]] << endl;
        else cout << 0 << endl;
        q[++tt] = i;
    }
    
}
  • 原本用的STL的队列没过
  • 然后改成静态没过
  • 然后又加了个二分,还是没过(多过了一个点)
  • 呜呜呜为什么要这样对待一个初学者
2024/10/30 14:55
加载中...