题目链接

Wooden Sticks POJ - 1065

思路

$$ \begin{aligned}贪心选取，证明用A <= B, A >= B,和调整法。\end{aligned} $$

时间复杂度

$$ O(Nlog(N)) $$

代码

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 5000 + 10;

int a[MAXN], b[MAXN], id[MAXN];
int f[MAXN];

bool cmp(int x, int y) {
    return a[x] < a[y];
}

int main() {
    int T;
    scanf("%d", &T);// don't forget &
    while (T--) {
        int n;
        scanf("%d", &n);// don't forget &
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &a[i], &b[i]);// don't forget &
            id[i] = i;
        }
        sort(id + 1, id + 1 + n, cmp);
        memset(f, 0, sizeof f);
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            int x = b[id[i]];
            int l = 1, r = n, cur = l;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (f[mid] <= x) {
                    cur = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            f[cur] = x;
            ans = max(ans, cur);
        }
        printf("%d\n", ans);
    }
    return 0;   
}