盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
    1. 二分 + RMQ
    2. Multiset
  4. 代码
    1. 二分 + RMQ
    2. Multiset
  5. 更新日志

CF 6E Exposition (二分, RMQ, set)

题目

源地址:http://codeforces.com/problemset/problem/6/E

题意

给定$n$个数,每个数为$h_i$,以及一个$k$。求最长的区间,使得该区间内所有数字的差值不超过$k$。第一行输出区间长度以及区间的个数,第二行输出每个区间$[l_i, r_i]$
数据范围:$1{\leq}n{\leq}10^5, 0{\leq}k, h_i{\leq}10^6$

思路

二分 + RMQ

首先用RMQ预处理出任意区间[l, r]的最大值和最小值。然后二分答案,如果该长度下,存在最大值减最小值的差值不超过$k$,便有解。

Multiset

也可以用Multiset来实现,从左到右依次将数字存入Multiset中。每加入一个数,如果此时出现最大值与最小值的差超过$k$,就要从头开始删数字,直到符合条件位置。

代码

二分 + RMQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
const int maxn = 1e5 + 10;
int n, k, mx[20][maxn], mn[20][maxn];
void RMQ(int num) {
for (int i = 1; i <= log2(num) + 1; i++)
for (int j = 1; j <= num; j++) if (j + (1 << i) - 1 <= num) {
mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << i >> 1)]);
mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << i >> 1)]);
}
}
int get(int st, int ed) {
int k = (int) log2(ed - st + 1.0);
int mxans = max(mx[k][st], mx[k][ed - (1 << k) + 1]);
int mnans = min(mn[k][st], mn[k][ed - (1 << k) + 1]);
return mxans - mnans;
}
bool check(int mid) {
for (int i = 1; i <= n - mid + 1; i++) {
if (get(i, i + mid - 1) <= k) return true;
}
return false;
}
int main () {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &mx[0][i]);
mn[0][i] = mx[0][i];
}
RMQ(n);
int l = 0, r = n, mid;
while(l < r) {
mid = (l + r) >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
if (l + 1 == r) break;
}
if (check(r)) l = r;
vector< pair<int, int> > g;
for (int i = 1; i <= n - l + 1; i++) {
if (get(i, i + l - 1) <= k) g.pb(make_pair(i, i + l - 1));
}
printf("%d %d\n", l, g.size());
for (int i = 0; i < g.size(); i++) cout<<g[i].first<<" "<<g[i].second<<endl;
return 0;
}

Multiset

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<iostream>
#include<set>
using namespace std;
const int N = 1e5 + 10;
multiset<int> s;
int n, k, h[N], r[N], mx, cnt, t;
int main () {
cin>>n>>k;
for (int i = 0; i < n; i++) {
scanf("%d", h + i);
s.insert(h[i]);
while(*s.rbegin() - *s.begin() > k) s.erase(s.find(h[t++]));
int len = i - t + 1;
if (len > mx) {
mx = len, cnt = 0;
r[cnt++] = t;
}
else if (len == mx) r[cnt++] = t;
}
cout<<mx<<" "<<cnt<<endl;
for (int i = 0; i < cnt; i++) printf("%d %d\n", r[i] + 1, r[i] + mx);
return 0;
}

更新日志

  • 2014-11-9 AC