40分求助

P1440 求m区间内的最小值

AnCangLan @ 2024-01-05 15:01:59

以下是代码：

#include <iostream>
using namespace std;

const int N = 2e6 + 1;

int main()
{
    ios::sync_with_stdio(false);
    long long n, m, a[N]{}, min = 0xffffff, p = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++)cin >> a[i];
    cout << 0 << endl;
    for (int i = 1; i < n; i++)
    {
        if (i - m <= 0)
        {
            min = (min >= a[i - 1] ? a[i - 1] : min);
            p = (min >= a[i - 1] ? i : p);
            cout << min << endl;
        }
        else if (p <= i - m)
        {
            min = 0xffffff;
            for (int j = i - m; j < i; j++)
            {
                min = (min >= a[j] ? a[j] : min);
                p = (min >= a[j] ? j : p);
            }
            cout << min << endl;
        }
        else
        {
            min = (min >= a[i] ? a[i] : min);
            p = (min >= a[i] ? i : p);
            cout << min << endl;
        }
    }

    return 0;
}

还有4个点WA，2个点TLE……（换scanf/printf也不行）方法只是对模拟的优化，省去了部分重复查找最小值的过程

by lovely_hyzhuo @ 2024-01-05 16:00:14

@AnCangLan 这题不是线段树？

by xiaoshumiao @ 2024-01-05 16:04:40

@lovely_hyzhuo 裸的单调队列啊

by _colin1112_ @ 2024-01-05 16:06:39

@AnCangLan 50分没TLE:

#include <iostream>
#include <cstdio>
#define endl '\n'
using namespace std;

const int N = 2e6 + 1;
long long n, m, a[N]{}, p = 0;
int main()
{
    long long min = 0xffffff;
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++)cin >> a[i];
    cout << 0 << endl;
    for (int i = 1; i < n; i++)
    {
        if (i - m <= 0)
        {
            min = (min >= a[i - 1] ? a[i - 1] : min);
            p = (min >= a[i - 1] ? i : p);
            cout << min << endl;
        }
        else if (p <= i - m)
        {
            min = 0xffffff;
            for (int j = i - m; j < i; j++)
            {
                min = (min >= a[j] ? a[j] : min);
                p = (min >= a[j] ? j : p);
            }
            cout << min << endl;
        }
        else
        {
            min = (min >= a[i] ? a[i] : min);
            p = (min >= a[i] ? i : p);
            cout << min << endl;
        }
    }

    return 0;
}

by lovely_hyzhuo @ 2024-01-05 16:07:35

@xiaoshumiao 线段树不是不能做，但是我T了

by lovely_hyzhuo @ 2024-01-05 16:12:35

@xiaoshumiao 我A了。

线段树要加快读......