首页 > itarticle > uva 1322 – minimizing maximizer

uva 1322 – minimizing maximizer

admin 11月 11, 2020 0

contents

Problem

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

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

Sample Input

Sample Output

Solution

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

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

#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); 
        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("%dn", ret);
        if (testcase)
            puts("");
    }
    return 0;
}
/*
*/