BZOJ1342 [Baltic2007]Sound静音问题

2015.01.16 08:30 Fri| 1 visits oi_2015| 2015_刷题日常| Text

Solution
Code

Solution

一道 $\mathcal O(n)$ 的水题，一道 $\mathcal O(n\log n)$ 的卡常数题……

据说 RMQ 会 TLE，用上 zkw 线段树才能 AC…… 但是看到这个题的时候想到 multimap 不是更加正常么……

Code

#include <bits/stdc++.h>
using namespace std;
#define N 1000005

multiset<int> s;
int n, m, c, a[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n >> m >> c;
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    for (int i = 1; i <= m; ++i)
        s.insert(a[i]);
    bool flag = false;
    for (int i = 1; i + m - 1 <= n; ++i)
    {
        if (*(--s.end()) - *s.begin() <= c)
            printf("%d\n", i), flag = true;
        s.erase(s.find(a[i]));
        s.insert(a[i + m]);
    }
    if (!flag) puts("NONE");
}