首页 > 代码库 > Wooden Sticks(hdu1051)
Wooden Sticks(hdu1051)
Wooden Sticks
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
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 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).
(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).
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 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.
Output
The output should contain the minimum setup time in minutes, one per line.
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 1Sample Output
2 1 3
//第一行是代表测试数据t
每组数据第一行是一个整数 n ，代表木头的数量
然后 n 对数据 代表 木头的长度，和重量
需要一个机器处理这些木棒，机器开启的时候需要耗费一个单位的时间，如果第i+1个木棒的重量和长度都大于等于
第i个处理的木棒，那么将不会耗费时间，否则需要消耗一个单位的时间。
问最短时间
//贪心解决了
排个序，就行
1 #include <stdio.h> 2 #include <iostream> 3 #include <algorithm> 4 using namespace std; 5 6 struct Node 7 { 8 int l,w; 9 }node[5005],setup[5005];10 11 bool cmp(Node a,Node b)12 {13 if (a.l==b.l)14 return a.w<b.w;15 return a.l<b.l;16 }17 18 int main()19 {20 int t;21 cin>>t;22 while (t--)23 {24 int n;25 int i,j;26 cin>>n;27 for (i=0;i<n;i++)28 {29 cin>>node[i].l>>node[i].w;30 }31 sort(node,node+n,cmp);32 int ans=1;33 setup[0].l=node[0].l;34 setup[0].w=node[0].w;35 36 for (i=1;i<n;i++)37 {38 int ok=0;39 for (j=0;j<ans;j++)40 {41 if (setup[j].l<=node[i].l&&setup[j].w<=node[i].w)42 {43 setup[j].l=node[i].l;44 setup[j].w=node[i].w;45 ok=1;46 break;47 }48 }49 if (ok==0)50 {51 setup[ans].l=node[i].l;52 setup[ans].w=node[i].w;53 ans++;54 }55 }56 cout<<ans<<endl;57 }58 return 0;59 }
Wooden Sticks(hdu1051)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。