|
题目：
Wooden Sticks |
| Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) |
| Total Submission(s): 2374 Accepted Submission(s): 921 |
| |
Problem DescriptionThere 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 1 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).
|
InputThe 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 magnitude at most 10000 , where li and wi are the length and weight of the i th wooden stick, respectively. The 2n integers are delimited by one or more spaces.
|
OutputThe output should contain the minimum setup time in minutes, one per line.
|
Sample Input3
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 Output2
1
3 |
| |
| SourceAsia 2001, Taejon (South Korea) |
题目大意：
给n根木棍的长度和重量。根据要求求出制作木棍的最短时间。建立第一个木棍需要1分钟，若是接着要制作的木棍重量和长度都比此木棍长就不需要建立的时间，若是没有，则再需要建立时间。求时间最小为多少。
题目分析：
一道贪心题，利用有序化数据进行贪心选择。其实就是求长度和重量都严格递增的数字序列的个数。
先按长度进行排序。排序完后的不一定都是下一根木棍重量和长度都大于前一根的。
代码如下：
/*
* f.cpp
*
* Created on: 2015年1月29日
* Author: Administrator
*/
#include
#include
#include
using namespace std; const int maxn = 5005; struct Node { int length; int weight; bool vis; } node[maxn]; bool cmp(Node a, Node b) { if (a.length != b.length) { return a.length < b.length; } return a.weight < b.weight; } void printNodes(Node nodes[], int n) { int i; for (i = 0; i < n; ++i) { printf("(%d,%d)\n", nodes[i].length, nodes[i].weight); } } int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); int i; for (i = 0; i < n; ++i) { scanf("%d%d", &node[i].length, &node[i].weight); node[i].vis = false; } sort(node, node + n, cmp);//先对数据进行排序 // printNodes(node,n);//用来测试排序以后的数据序列 int ans = 0;//最后的长度和重量都严格递增的数列的个数 int j; for (i = 0; i < n; ++i) {//遍历这个数列中的每一个数 if (node[i].vis == false) {//如果这一个数还没有被访问过 node[i].vis = true;//那么将这个鼠标纪委已经访问 ans++;//结果+1 int weight = node[i].weight ;//标记当前的重量 for (j = i + 1; j < n; ++j) {//扫描当前元素后面的所有元素 //如果后面的元素没有被访问过&&后面的元素比当前元素的重量大 (因为排序以后长度默认已经是升序) if ((node[j].vis == false) && (node[j].weight >= weight)) { node[j].vis = true;//将该元素标记为已经访问过 weight = node[j].weight;//并且更新当前的重量值 } } } } printf("%d\n", ans); } return 0; }
|