Wooden Sticks
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 9541 Accepted Submission(s): 3917
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 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 1
Sample Output
2
1
3
好吧，这是一道简单题，，，仔细点就好；
思路是；把木棍按照长度优先从小到大排好，当长度一定是按宽度从小到大排好，然后比较宽度就ok了
，具体见代码，，，，
简单易懂型：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int l;
int w;
int k;
}a[]; int main()
{
int T,n,j,i,temp,sum,p;
scanf("%d",&T);
while(T--)
{
sum=;
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%d%d",&a[i].l,&a[i].w);
a[i].k=;//标记
}
for(i=;i<=n;i++)//选择 why!!!
{
p=i;
for(j=i+;j<=n;j++)
if(a[p].l>a[j].l||a[p].l==a[j].l&&a[p].w>a[j].w) //长度优先排，然后是宽度，都排好，从小到大
p=j;
if(p!=i)
{
int t;
t=a[i].l;
a[i].l=a[p].l;
a[p].l=t;
t=a[i].w;
a[i].w=a[p].w;
a[p].w=t;
}
}
// for(i=1;i<=n;i++)
// printf("%d %d %d \n",a[i].l,a[i].w,a[i].k);
for(i=;i<=n;i++)
{
if(a[i].k==)
{
temp=a[i].w;
for(j=i+;j<=n;j++)
{
if(a[j].w>=temp&&a[j].k==)
{
a[j].k=;
temp=a[j].w;
sum++;
} }
}
}
printf("%d\n",n-sum);
}
return ;
} /*
4
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
7
1 12 1 5 2 6 2 8 2 4 4 3 3 7 */
然后是更加简洁的排序sort，快排。。。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int l;
int w;
int k;
}a[]; int cmp(node a,node b)
{
if(a.w==b.w)
return a.l<b.l;
return a.w<b.w;
} int main()
{
int T,n,j,i;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(i=;i<n;i++)
{
scanf("%d%d",&a[i].l,&a[i].w);
a[i].k=;//标记
}
sort(a,a+n,cmp);
for(i=;i<n;i++)
printf("%d %d %d \n",a[i].l,a[i].w,a[i].k); int num=n;
int count=;
while(num)
{
int tl=;int tw=;
for(i=;i<n;i++)
{
if(a[i].k==&&a[i].w>=tw&&a[i].l>=tl)
{
tl=a[i].l; tw=a[i].w; a[i].k=;num--;
}
}
count++;
}
printf("%d\n",count);
}
return ;
}
稍作修改：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int l;
int w;
int k;
}a[]; int cmp(node a,node b)//从小到大排，，，对于结构体
{
if(a.l==b.l)
return a.w<b.w;
return a.l<b.l;
}
int main()
{
int T,n,j,i,temp,sum;
scanf("%d",&T);
while(T--)
{
sum=;
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%d%d",&a[i].l,&a[i].w);
a[i].k=;//标记
}
sort(a+,a+n+,cmp);
for(i=;i<=n;i++)
printf("%d %d %d \n",a[i].l,a[i].w,a[i].k);
for(i=;i<=n;i++)
{
if(a[i].k==)
{
temp=a[i].w;
for(j=i+; j<=n; j++)
{
if(a[j].w>=temp&&a[j].k==)
{
a[j].k=;
temp=a[j].w;
sum++;
} }
}
}
printf("%d\n",n-sum);
}
return ;
}
是的，冒泡嘛，也是可以的，，，
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int l;
int w;
int k;
}a[]; int cmp(node a,node b)
{
if(a.l==b.l)
return a.w<b.w;
return a.l<b.l;
}
int main()
{
int T,n,j,i,temp,sum;
scanf("%d",&T);
while(T--)
{
sum=;
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%d%d",&a[i].l,&a[i].w);
a[i].k=;//标记
}
for(i=;i<=n;i++)//冒泡
{
for(j=;j<n-i;j++)//j从1开始就错了。。。
if(a[j].l>a[j+].l)
{
int vv;
vv=a[j].w; a[j].w=a[j+].w; a[j+].w=vv;
vv=a[j].l; a[j].l=a[j+].l; a[j+].l=vv; }
} for(i=;i<=n;i++)
printf("%d %d %d \n",a[i].l,a[i].w,a[i].k);
for(i=;i<=n;i++)
{
if(a[i].k==)
{
temp=a[i].w;
for(j=i+; j<=n; j++)
{
if(a[j].w>=temp&&a[j].k==)
{
a[j].k=;
temp=a[j].w;
sum++;
} }
}
}
printf("%d\n",n-sum);
}
return ;
}
推荐第二种，，，，本题还可以用dp做，具体代码，有待有序更新。。。o(∩_∩)o 哈哈