superman

聚精会神搞建设 一心一意谋发展
posts - 190, comments - 17, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

ZOJ 1025 - Wooden Sticks

Posted on 2008-03-26 23:38 superman 阅读(512) 评论(0)  编辑 收藏 引用 所属分类: ZOJ
 1 /* Accepted 1025 C++ 00:00.16 924K */
 2 #include <string.h>
 3 #include <iostream>
 4 
 5 using namespace std;
 6 
 7 struct Stick { int l, w; } stick[5000];
 8 
 9 int cmp(const void * a, const void * b)
10 {
11     Stick * c = (Stick*) a;
12     Stick * d = (Stick*) b;
13     if(c -> l == d -> l)
14         return c -> w - d -> w;
15     return c -> l - d -> l;
16 }
17 
18 int main()
19 {
20     int n;
21     cin >> n;
22     while(cin >> n)
23     {
24         for(int i = 0; i < n; i++)
25             cin >> stick[i].l >> stick[i].w;
26         
27         qsort(stick, n, sizeof(Stick), cmp);
28         
29         bool x[5000= {0};
30         int count = 0, m = n;
31         while(m)
32         {
33             int k, curL, curW;
34             for(k = 0; k < n; k++)
35                 if(x[k] == 0)
36                     break;
37             curL = stick[k].l;
38             curW = stick[k].w;
39             for(int i = k; i < n; i++)
40                 if(x[i] == 0)
41                     if(stick[i].l >= curL && stick[i].w >= curW)
42                     {
43                         m--;
44                         x[i] = 1;
45                         curL = stick[i].l;
46                         curW = stick[i].w;
47                     }
48             count++;
49         }
50         
51         cout << count << endl;
52     }
53     
54     return 0;
55 }
56 

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