UVAlive 2322 (13.08.23)

There is a pile of n wooden sticks. The length and weight ofeach stick are known in advance. The sticks areto be processed by a woodworking machine in one by one fashion. Itneeds some time, called setup time, forthe machine to prepare processing a stick. The setup times areassociated with cleaning operations andchanging tools and shapes in the machine. The setup times of thewoodworking machine are given as follows:

• The setup time for the first woodenstick is 1 minute.
• Right after processing a stick of length l and weight w, the machine will need no setup time for a stickof lengthl' and weight w' if l <=l'and w <=w' .

Otherwise, it will need 1 minute for setup.
You are to find the minimum setup time to process a given pile of nwooden sticks. For example, if you havefive sticks whose pairs of length and weight are (4,9), (5,2), (2,1), (3,5),and (1,4) then the minimum setuptime should be 2 minutes since there is a sequence of pairs (1,4),(3,5), (4,9), (2,1), (5,2).

Input

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Eachtest case consists of two lines: The first line has an integern,1<=n<=5000, that represents the number ofwooden sticks in the test case, and the second line contains 2npositiveintegers l₁, w₁, l₂,w₂, ...,l_n, w_n,each of magnitude at most 10000, wherel_i and w_iare the length and weight of thei th wooden stick,respectively. The 2n integers are delimited by one ormore spaces.

Output

The output should contain the minimum setup time in minutes, one perline.

Sample Input

3
5
4 9 5 2 2 1 3 5 1 4
3
2 2 1 1 2 2
3
1 3 2 2 3 1

Sample Output

2
1
3

题意:

有点说不清楚, 我简单点说就是排序, 拿样例的第一组来说

我们要做到: 下一根木棍的长度l和重量w 都要比 当前根来的大

看第一组样例最后排成的序列 (1,4),(3,5),(4,9),(2.1),(5.2)

显然前三个木棍是符合要求的, 然后(4,9) 和 (2,1) 明显不符合要求, 那么就停止, 前三根木棍算重新设置了一下, 编成了一组

然后 将(2,1),(5,2)再继续设置, 如此往复, 求最少设置了几次~?

做法:

按长度从小到大排序, 若长度相同, 则按重量从小到大排序(先按重量再按长度也行)

然后, 我们针对当前木棍, 与剩下的木棍比较, 满足 w1 <= w2 && l1 <= l2 的, 就更新一下当前棍, 并标记~

当所有木棍都被编组后 输出到底设置了几次~

AC代码:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>

using namespace std;

struct Point{
    int l;
    int w;
    int mark;
}point[5555];

int cmp(Point a, Point b) {
    if(a.l != b.l)
        return a.l < b.l;
    return a.w <= b.w;
}

int main() {
    int T;
    scanf("%d", &T);

    while(T--) {
        int n;
        scanf("%d", &n);

        int time = 0;
        memset(point, 0, sizeof(point));
        for(int i = 0; i < n; i++)
            scanf("%d %d", &point[i].l, &point[i].w);

        sort(point, point+n, cmp);

        int tmp;
        for(int i = 0; i < n; i++) {
            if(point[i].mark)
                continue;
            time++;
            tmp = point[i].w;
            for(int j = i; j < n; j++) {
                if(point[j].w >= tmp && point[j].mark == 0) {
                    tmp = point[j].w;
                    point[j].mark = 1;
                }
            }
        }
        printf("%d\n", time);
    }
    return 0;
}