BZOJ1342 [Baltic2007]Sound静音问题
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"); }