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' .
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 integer
n,1<=
n<=5000, that represents the number ofwooden sticks in the test case, and the second line contains 2
npositiveintegers
l1,
w1,
l2,
w2, ...,
ln,
wn,each of magnitude at most 10000, where
li and
wiare the length and weight of the
i th wooden stick,respectively. The 2
n 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
", time);
}
return 0;
}