鼠鼠再怎么优化也过不了这个单调队列

kendas @ 2024-10-30 14:55:35

#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;
    }

}

by kendas @ 2024-10-30 15:03:16

哈哈我上早八，改了这么久原来是cin太慢了，我真的想****

我真的，真的****

我把cin改scanf，cout改printf快了近10倍，原本1.5s都没跑完现在230多ms跑完了没过的点，哈哈，我真的，哈哈，hh，我真服了哈哈，日

cin//NO
scanf//YES
cout//NO
printf//YES

思来想去，我真2b,hh

by kendas @ 2024-10-30 15:09:05

楼主你是2b吧，真看不下去了哈哈

cin -> scanf
cout -> printf

这都不知道你无敌了孩子

by Goodans @ 2024-10-30 15:44:12

ios::sync_with_stdio(0);
cin.tie(nullptr),cout.tie(nullptr);

@kendas 你可知道io优化

by zhang_jun @ 2024-10-30 15:46:00

@kendas 你可以在主函数最前面加上以下语句：

ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);

这样的话，cin和cout就应该不会超时了。

但加了之后不能混用C/C++风格输入输出

by kendas @ 2024-10-30 16:34:04

@zhang_jun ???！还有这种东西?要不是cin输入输出方便初学者也不会选择这个，有了这个不是爽完

by kendas @ 2024-10-30 19:38:36

@kendas 我靠？！突然想到为什么可以用二分呢？数据是不是有问题？二分条件不是数组内数据是有序的吗？！！我刚才试了另外一个简单的滑动窗口问题，过不了！

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;
}

by dg114514 @ 2025-01-04 19:42:42

@kendas你不知道endl很耗时吗？用"\n"