学步园

这几题的思想和方法都是一样的，破一题可破三题，首先1065，题意说有很多stick，每个stick都有长度l和重量w,一台机器需要处理这些stick，首先第一条被处理的机器就需要一次setup time,接下来下根木棍的长度l和w都大于等于前面的木棍的话，那么就不需要增加setup time,否者需要，问一堆木棍处理完需要最少的setup time是多少，首先它如果大于就不需要setup time，然后就想到了排序，按l排序，如果l相等的话就按w排序，也就是说排序后保证了l是非递减序列，这时候判断w是否大与等于前面的w，如果是就把他们放入同一个set time的队列并标记这个stick不需要set time,依此类推，最后多少个队列就代表了最少的set time的次数。

#include<iostream><br /> using namespace std;<br /> const int MAX = 50005;<br /> int n;<br /> bool mark[MAX];<br /> struct sticks<br /> {<br /> int l;<br /> int w;<br /> }st[MAX];<br /> int cmp( const void *a , const void *b )<br /> {<br /> if((*(sticks *)a).l!=(*(sticks *)b).l)<br /> return (*(sticks *)a).l-(*(sticks *)b).l;<br /> else<br /> return (*(sticks *)a).w-(*(sticks *)b).w;<br /> }<br /> void min_time()<br /> {<br /> qsort(st,n,sizeof(st[0]),cmp);</p> <p> int i,temp,times=0,j;<br /> memset(mark,0,n);<br /> for(i=0;i<n;i++)<br /> {<br /> if(mark[i]==0)<br /> {<br /> times++;<br /> temp=st[i].w;<br /> for(j=i+1;j<n;j++)<br /> {<br /> if(st[j].w>=temp&&mark[j]==0)<br /> {<br /> mark[j]=1;<br /> temp=st[j].w;<br /> }</p> <p> }<br /> }<br /> }<br /> cout<<times<<endl;<br /> }<br /> int main()<br /> {<br /> int T,i;<br /> cin>>T;<br /> while(T--)<br /> {<br /> cin>>n;<br /> for(i=0;i<n;i++)<br /> cin>>st[i].l>>st[i].w;<br /> min_time();<br /> }<br /> return 0;<br /> }<br />

PKU 1548和1065几乎一样。

PKU 3636和前面两题的区别只是等于的情况也需要set time 所以排序要做修改，

例如下面的情况

1 2

2 3

2 6

3 4

如果这样排就导致最少需要3次，因为2 6这里需要后3 4又需要，所以这时把 2 6排在2 3前面就可以避免这种情况的发生，就是当w相等时候，h按降序排序即可

#include<iostream><br /> using namespace std;<br /> const int MAX = 20005;<br /> int m;<br /> bool mark[MAX];<br /> struct sticks<br /> {<br /> int l;<br /> int w;<br /> }st[MAX];<br /> int cmp( const void *a , const void *b )<br /> {<br /> if((*(sticks *)a).l!=(*(sticks *)b).l)<br /> return (*(sticks *)a).l-(*(sticks *)b).l;<br /> else<br /> return -((*(sticks *)a).w-(*(sticks *)b).w);<br /> }<br /> void min_time()<br /> {<br /> qsort(st,m,sizeof(st[0]),cmp);</p> <p> int i,temp,times=0,j,temp2;</p> <p> memset(mark,0,m);<br /> for(i=0;i<m;i++)<br /> {<br /> if(mark[i]==0)<br /> {<br /> times++;<br /> temp=st[i].w;<br /> temp2=st[i].l;<br /> for(j=i+1;j<m;j++)<br /> {<br /> if(st[j].w>temp&&mark[j]==0&&st[j].l>temp2)<br /> {<br /> mark[j]=1;<br /> temp=st[j].w;<br /> temp2=st[j].l;<br /> }</p> <p> }<br /> }<br /> }<br /> printf("%d/n",times);<br /> }<br /> int main()<br /> {<br /> int t,i;<br /> scanf("%d",&t);<br /> while(t--)<br /> {<br /> scanf("%d",&m);<br /> for(i=0;i<m;i++)<br /> scanf("%d%d",&st[i].l,&st[i].w);<br /> min_time();<br /> }<br /> return 0;<br /> }<br />