pku 1065

 

 1 #include <cstdio>
 2 #include <malloc.h>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 struct nod
 7 {
 8  int l;
 9  int w;
10  bool n;
11 };
12 
13 int q_sort( nod *s3[5001],int q_head,int q_rear ) // 快排
14 {
15  int i = q_head-1;
16  int j = q_head;
17  for ( ; j < q_rear; ++j )
18  {
19   if ( s3[j]->< s3[q_rear]->l  )
20   {
21    ++i;
22    swap( s3[i]->l,s3[j]->l );
23    swap( s3[i]->w,s3[j]->w );
24   }
25   else if ( s3[j]->== s3[q_rear]->l )
26   {
27    if ( s3[j]->< s3[q_rear]->w )
28     swap( s3[j]->w,s3[q_rear]->w ); // 重点: 当两个长度相等时,要把重量按升序排列,因为这样才不会导致后来会少算!!!
29 
30   }
31 
32  }
33  swap( s3[i+1]->l,s3[q_rear]->l );
34  swap( s3[i+1]->w,s3[q_rear]->w );
35  return i+1;
36 }
37    
38 
39   
40 
41 void sort( nod *s2[5001],int head,int rear )
42 {
43  int i;
44  if ( head < rear )
45  {
46   i = q_sort( s2,head,rear );
47   sort( s2,head,i-1 );
48   sort( s2,i+1,rear );
49  }
50 }
51 
52 
53 int main()
54 {
55  //freopen( "in.txt","r",stdin );
56  int y;
57  scanf( "%d",&y );
58  while ( y != 0 )
59  {
60   int m;
61   scanf ( "%d",&m );
62   nod *s1[5001];
63   int l,w;
64   for ( int i = 0; i != m; ++i )
65   {
66    s1[i] = ( nod * )malloc( sizeof( nod ) );
67    scanf ( "%d%d",&l,&w );
68    s1[i]->= l;
69    s1[i]->= w;
70    s1[i]->= false;
71   }
72   sort( s1,0,m-1 );
73   int time = 0;
74   for ( int i = 0; i != m; ++i ) // 贪心
75   {
76    if ( s1[i]->== false )
77    {
78     int j = i;
79     int k = s1[i]->w;
80     while ( j != m )
81     {
82      if ( s1[j]->== false && s1[j]->>= k  )
83      {
84       s1[j]->= true;
85       k = s1[j]->w;
86      }
87      ++j;
88     }
89     ++time;
90    }
91   }
92   printf ( "%d\n",time );
93   --y;
94  }
95  return 0;
96 }
97 

posted on 2010-03-22 14:41 haozi 阅读(153) 评论(0)  编辑 收藏 引用 所属分类: 贪心


只有注册用户登录后才能发表评论。
相关文章:
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年6月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜