# UVA11039-Building designing

Time limit: 3.000 seconds

An architect wants to design a very high building. The building will consist of some ﬂoors, and each ﬂoor has a certain size. The size of a ﬂoor must be greater than the size of the ﬂoor 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 ﬂoor a colour, and in such a way that the colours of two consecutive ﬂoors are diﬀerent. To design the building the architect has n available ﬂoors, with their associated sizes and colours. All the available ﬂoors are of diﬀerent sizes. The architect wants to design the highest possible building with these restrictions, using the available ﬂoors. Input The input ﬁle consists of a ﬁrst line with the number p of cases to solve. The ﬁrst line of each case contains the number of available ﬂoors. Then, the size and colour of each ﬂoor appear in one line. Each ﬂoor is represented with an integer between -999999 and 999999. There is no ﬂoor with size 0. Negative numbers represent red ﬂoors and positive numbers blue ﬂoors. The size of the ﬂoor is the absolute value of the number. There are not two ﬂoors with the same size. The maximum number of ﬂoors for a problem is 500000. Output For each case the output will consist of a line with the number of ﬂoors 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

``` 1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
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;
40     while(t--)
41     {
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 }```

``` 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 条评论

## 相关文章

21380

69850

### Golang之匿名函数和闭包

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

33510

9620

38470

41670

378100

34450

13930

### Go语言的fmt包中文教程

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

45170