codevs 4888 零件分组

2018-06-17 22:44:19来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

4888 零件分组

 

 时间限制: 1 s
 空间限制: 16000 KB
 题目等级 : 黄金 Gold
 
 
题目描述 Description

现有一些棍状零件,每个零件都有一定的长度(Li)和重量(Wi)。现在为了加工需要,要将他们分成若干组,使每一组中的零件都能排成一个长度和重量都不下降(若i<j,则Li<=Lj,Wi<=Wj,其中i,j为在同一组中的序号)的序列。请问至少要分成几组?

输入描述 Input Description

第1行为一个整数n,表示棍状零件的总个数。

接下来n行每行有两个正整数,分别为一个零件的长度(Li)和重量(Wi)。

输出描述 Output Description

输出一个正整数,表示最小分成的组数

样例输入 Sample Input

5

8 4

3 8

9 7

2 3

3 5

样例输出 Sample Output

2

 

解释:

第一组

(2,3) (3,5) (3,8)

第二组

(8,4)(9,7)

数据范围及提示 Data Size & Hint

n<=1000

Wi<=10000

Li<=10000

分类标签 Tags 点此展开 

发现sort是万能的,,,,,,,,

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=10001;
 7 struct node
 8 {
 9     int x;
10     int y;
11 }map[MAXN];
12 int now=0;
13 int comp(const node & a,const node & b)
14 {
15     if(a.x>b.x&&a.y>b.y)
16     return 1;
17     else
18     return 0;
19 }
20 int main()
21 {
22     int n;
23     scanf("%d",&n);
24     for(int i=1;i<=n;i++)
25     {
26         scanf("%d%d",&map[i].x,&map[i].y);
27     }
28     sort(map+1,map+n+1,comp);
29     int tot=1;
30     for(int i=1;i<=n;i++)
31     {
32         if(map[i].x<=map[i+1].x)
33         tot++;
34     }
35     printf("%d",tot);
36     return 0;
37 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:第一站:CLion安装教程与环境配置

下一篇:Hello World另类写法