UVa 1322 - Minimizing Maximizer

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

有一個 Sorter 可以排序區間 [l, r],按照順序挑選 Sorter,使得可以在序列中找到最大值。

記住,請按照輸入順序使用,否則可以直接貪心掃描。

Sample Input

1
2
3
4
5
6
7
8
9
1
40 6
20 30
1 10
10 20
20 30
15 25
30 40

Sample Output

1
4

Solution

如果要求按照順序,則必然在前 i 個 Sorter,紀錄覆蓋 [1, r] 的最小值。

那麼當提供一個 Sorter 支持 [x, y],則查找覆蓋 [1, r] 其中 r >= x 的條件下的最小值。看到符合前綴最小值的操作,套用 binary indexed tree 來進行極值查找。否則線性搜索很容易超時。

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
45
46
47
48
49
50
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <functional>
#include <deque>
#include <assert.h>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 65536
int BIT[MAXN];
void modify(int x, int val, int L) {
while (x <= L) {
BIT[x] = min(BIT[x], val);
x += x&(-x);
}
}
int query(int x) {
int ret = INF;
while (x) {
ret = min(ret, BIT[x]);
x -= x&(-x);
}
return ret;
}
int main() {
int testcase, N, M, x, y;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %d", &N, &M);
vector< pair<int, int> > D;
for (int i = 0; i <= N; i++)
BIT[i] = INF;
modify(N, 0, N); // [1, 1] => 0
for (int i = 0; i < M; i++) {
scanf("%d %d", &x, &y);
int val = query(N - x + 1) + 1;
modify(N - y + 1, val, N);
}
int ret = query(1);
printf("%d\n", ret);
if (testcase)
puts("");
}
return 0;
}
/*
*/