Home » Java » HDU 1051 Wooden S

HDU 1051 Wooden S

Time, Limit:, 2000/1000, MS (Java/Others), Memory, Limit:, 65536/32768, K (Java/Others)

Total Submission (s): 5883, Accepted, Submission (s): 2438


Problem Description

There is a pile of N wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:


(a), The, setup, time, for, the, first, wooden, stick, is,,, minute.,

(b) Right after processing a stick of length L and weight W, the machine will need no setup time for a stick of length L 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 N wooden sticks. For example, if you have five sticks whose pairs of length and weight are (4,9), (5,2), (2,1), (3,5), and (1,4), then the minimum setup time 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. Each test case consists of two lines: The first line has an integer n, 1<=n<=5000 that, represents the number of wooden sticks in the test case, and the second line contains N 2 positive integers L1 W1, L2, W2,... LN, WN, each, of, at, most, WI, where, Li, and, are, the, length, and, weight, of, the, I, th, wooden, stick, respectively., The, 2n,, integers, are,, delimited, by,, one, magnitude, or, more, spaces.


Output

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


Sample Input

3

5

49522135, 14,

3

221122

3

13223 1


Sample Output

2

1

3


subject:


to the length and weight of N stick. The shortest time making sticks calculated according to requirements. The establishment of the first stick to 1 minutes, if you stick to the weight and length of then are produced than the long stick does not need to establish the time, if not, then need to build for the minimum time for many time..


problem solving thinking:


on the stick length and weight are sorted by length for first consideration. After sorting is not necessarily stick the weight and length of a is greater than the previous one. Then, we repeatedly scanning the sorted array, will be in a period of time to complete the establishment of the mark what sticks all markers (the number of setting an external variable to count the scanned elements).


example:


5


4 95221351, 4


after sorting:


1 42135495, 2


then scans for the first time: the mark[] array is used to mark, mark[] initializes to 0, and red is the first.

to be traced

Stiks: (14) (21) (35) (49) (52), (

)

Mark:1 011, 0


this is the time required for setuptime to build the first stick, that is, 1, at which time the scan count is 3


followed second scans, with blue as the result of second scans,.


Stiks: (14) (21) (35) (49) (52), (

)

Mark:1 011, 0


, this is setuptime, 1, and the scan count is 5


code



Import java.util.Scanner;
Public, class, Main {
/ * *
* @param args
* /
Static int n;
Class Node{
Int x;
Int y;
Boolean vis;
}
Static Node e[]=new Node[5000];
Public, static, void, main (String[], args) {
Auto-generated method stub / / TODO
Scanner scan=new Scanner (System.in);
Int t;
T=scan.nextInt ();
While (t>0) {
Int ans=0;
Int count=0;
N=scan.nextInt ();
For (int i=0; iInt, a=scan.nextInt ();
Int, b=scan.nextInt ();
Main, hdu=new, Main ();
Node, node=hdu.new, Node ();
Node.x=a;
Node.y=b;
Node.vis=false;
E[i]=node;
}
/ / sort
Sort ();
Int P1 = 0;
While (count, =n) {
For (int i=0; iIf ({e[i].vis) {
P1=i;
Ans++;
Break;
}
}
For (int i=0; iIf ({e[i].vis&&e[i].x>=e[p1].x&&e[i].y>=e[p1].y) {
Count++;
E[i].vis=true;
P1=i;
}
}
}
System.out.println (ANS);
T--;
}
}
Private, static, void, sort () {
Auto-generated method stub / / TODO
For (int i=0; iFor (int j=0; jIf (e[j].x>e[j+1].x) {
Int temp=e[j].x;
E[j].x=e[j+1].x;
E[j+1].x=temp;
Int temp1=e[j].y;
E[j].y=e[j+1].y;
E[j+1].y=temp1;
}
}
}
}
}

Latest