UVA 11039-Building designing【贪心+绝对值排序】 UVA11039-Building designing

UVA11039-Building designing

Time limit: 3.000 seconds

An architect wants to design a very high building. The building will consist of some floors, and each floor has a certain size. The size of a floor must be greater than the size of the floor immediately above it. In addition, the designer (who is a fan of a famous Spanish football team) wants to paint the building in blue and red, each floor a colour, and in such a way that the colours of two consecutive floors are different. To design the building the architect has n available floors, with their associated sizes and colours. All the available floors are of different sizes. The architect wants to design the highest possible building with these restrictions, using the available floors. Input The input file consists of a first line with the number p of cases to solve. The first line of each case contains the number of available floors. Then, the size and colour of each floor appear in one line. Each floor is represented with an integer between -999999 and 999999. There is no floor with size 0. Negative numbers represent red floors and positive numbers blue floors. The size of the floor is the absolute value of the number. There are not two floors with the same size. The maximum number of floors for a problem is 500000. Output For each case the output will consist of a line with the number of floors of the highest building with the mentioned conditions. Sample Input 2

5

7

-2

6

9

-3

8

11

-9

2

5

18

17

-15

4 Sample Output 2

5

题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1980

题意:建一栋楼,负数代表一种颜色,正数代表另一种颜色,要正负号交替且绝对值递增。

两种解法:

第一种就是简单排下序,然后贪心的思想不断找绝对值最小的就可以了,注意的就是先取正值和先取负值的情况都要考虑

还有一种就是直接对绝对值进行排序操作,然后标记正负号(貌似更简练,感谢欧尼酱的点播)

解法1AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 inline int read()
 5 {
 6     int x=0,f=1;
 7     char ch=getchar();
 8     while(ch<'0'||ch>'9')
 9     {
10         if(ch=='-')
11             f=-1;
12         ch=getchar();
13     }
14     while(ch>='0'&&ch<='9')
15     {
16         x=x*10+ch-'0';
17         ch=getchar();
18     }
19     return x*f;
20 }
21 inline void write(int x)
22 {
23     if(x<0)
24     {
25         putchar('-');
26         x=-x;
27     }
28     if(x>9)
29     {
30         write(x/10);
31     }
32     putchar(x%10+'0');
33 }
34 const int N=555555;
35 int a[N],b[N];
36 int main()
37 {
38     int t,n,p1,p2,num;
39     t=read();
40     while(t--)
41     {
42         n=read();
43         p1=0;
44         p2=0;
45         for(int i=1;i<=n;i++)
46         {
47             scanf("%d",&num);
48             if(num>0)
49                 a[p1++]=num;
50             else
51                 b[p2++]=-num;
52         }
53         sort(a,a+p1);
54         sort(b,b+p2);
55         int m1=0,m2=0,n1=1,n2=1;
56         while(m1<p1&&m2<p2)
57         {
58             while(m2<p2&&b[m2]<=a[m1])
59                 m2++;
60             if(m2!=p2)
61                 n1++;
62             else
63                 break;
64             while(m1<p1&&a[m1]<=b[m2])
65                 m1++;
66             if(m1!=p1)
67                 n1++;
68             else
69                 break;
70         }
71         m1=0,m2=0;
72         while(m1<p1&&m2<p2)
73         {
74             while(m1<p1&&a[m1]<=b[m2])
75                 m1++;
76             if(m1!=p1)
77                 n2++;
78             else
79                 break;
80             while(m2<p2&&b[m2]<=a[m1])
81                 m2++;
82             if(m2!=p2)
83                 n2++;
84             else
85                 break;
86         }
87         printf("%d\n",max(n1,n2));
88     }
89     return 0;
90 }

解法2AC代码:(欧尼酱的代码,参考一下)

 1 #include<bits/stdc++.h>
 2 const int N=5*1e5+10;
 3 using namespace std;
 4 int a[N];
 5 bool cmp(int a,int b)
 6 {
 7     return abs(a)<abs(b);
 8 }
 9 int main()
10 {
11     int t,n,flag,num;
12     while(~scanf("%d",&t))
13     {
14         while(t--)
15         {
16             scanf("%d",&n);
17             flag=0;
18             num=0;
19             for(int i=0;i<n;i++)
20                 scanf("%d",&a[i]);
21             sort(a,a+n,cmp);
22             if(a[0]>0)
23                 flag=1;
24             else 
25                 flag=2;
26             num++;
27             for(int i=1;i<n;i++)
28             {
29                 if(flag==1)
30                 {
31                     if(a[i]<0)
32                     {
33                         flag=2;
34                         num++;
35                     }
36                 }
37                 else if(flag==2)
38                 {
39                     if(a[i]>0)
40                     {
41                         flag=1;
42                         num++;
43                     }
44                 }
45              }
46           printf("%d\n",num);
47         }
48     }
49     return 0;
50 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IMWeb前端团队

bash 的字符串和数组

回顾下自己接触过的编程语言,字符串和数组真是基础中的基础。也因此,在接触一门新的语言的时候,非常有必要去熟悉该语言的字符串和数组。 字符串 声明和赋值 name...

21380
来自专栏Golang语言社区

Go语言实现的排列组合问题实例(n个数中取m个)

本文实例讲述了Go语言实现的排列组合问题。分享给大家供大家参考,具体如下: (一)组合问题 组合是一个基本的数学问题,本程序的目标是输出从n个元素中取m个的所有...

69850
来自专栏Pythonista

Golang之匿名函数和闭包

 基本概念 闭包是可以包含自由(未绑定到特定对象)变量的代码块,这些变量不在这个代码块内或者 任何全局上下文中定义,而是在定义代码块的环境中定义。要执行的代码块...

33510
来自专栏程序生活

Leetcode-Easy 806. Number of Lines To Write String

给一个字符串S,从左到右将它们排列行,每行最大长度为100,,同时给定一个数组withds,widths[0]对应着 a的宽度, widths[1]对应着b的宽...

9620
来自专栏Golang语言社区

Golang中Interface类型详解

本文章翻译自《Let's learn Go》的“Interfaces: the awesomesauce of Go”一节 原文地址:http://go-bo...

38470
来自专栏python学习指南

python切片

本篇将介绍Python的切片操作,切片支持的数据类型有列表、字符串、元祖,更多内容请参考:Python学习指南 切片是什么? 切片操作符是序列名后跟一个方...

41670
来自专栏Golang语言社区

Golang中Interface类型详解

文 | Zuozuohao 共 14470 字,阅读需 36 分钟 本文章翻译自《Let's learn Go》的“Interfaces: the awesom...

378100
来自专栏ml

排序

排序法 平均时间 最差情形 稳定度 额外空间 冒泡 O(n2)     O(n2) 稳定 O(1) 交换     O(n2)     O(n2) ...

34450
来自专栏一个会写诗的程序员的博客

Kotlin 语言中的“关键字” Keywords in Kotlin修饰符关键字

但在 kotlin, 有一些关键字在某些情况下可以用作标识符。 在 kotlin 中基本上有四种类型的关键字:

13930
来自专栏Golang语言社区

Go语言的fmt包中文教程

Fmt包 import "fmt" 简介 ▾ Package fmt包含有格式化I/O函数,类似于C语言的printf和scanf。格式字符串的规则来源于C但更...

45170

扫码关注云+社区

领取腾讯云代金券