一道OI问题

回复帖子

@wkjwkj 2020-03-26 21:02 回复

下面这道题是我自己出的

这里

我已经知道了当n,m范围较小的时候能用队列+sort解决,但当数据大时貌似不行,请教大佬们有没有更好的算法。

@S1nner  2020-03-26 21:56 回复 举报

@wkjwkj

#include <bits/stdc++.h>

const int MAXN = 1e5;
int N, M;
std::pair < int, int > a[MAXN + 7];
int f[MAXN + 7], g[MAXN + 7];

inline int max(int x, int y) { return x > y ? x : y; }

void prepare() {
    f[N] = g[N] = N + 1;
    for (int i = N - 1; i; --i) {
        f[i] = f[i + 1], g[i] = g[i + 1];
        if (a[i + 1].second >= 0) f[i] = i + 1;
        if (a[i + 1].second <= 0) g[i] = i + 1;
    }
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; ++i)
        scanf("%d %d", &a[i].first, &a[i].second);
    std::sort(a + 1, a + N + 1);
    prepare();
    int res = 0, ans =0;
    for (int i = 1, j = 0; i <= N; ++i) {
        if (i > j)
            j = i, res = a[i].second == 0;
        while (j < N && a[j + 1].first - a[i].first + 1 <= M) {
            ++j;
            if (a[j].second == 0 || a[j].second * a[j - 1].second < 0)
                ++res;
        }
        ans = max(ans, res);
        if ((a[i].second > 0 && g[i] <= j) || (a[i].second < 0 && f[i] <= j) || a[i].second == 0)
            --res;
    }
    std::cout << ans << '\n';
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。