UVa 11039 设计建筑物

题意：

有n个绝对值各不相同的非0整数，选出尽量多的数，排成一个序列，使得正负号交替且绝对值递增。

思路：
正数存一个数组，负数存一个数组，排序后进行遍历即可。

 1 #include<iostream> 
 2 #include<algorithm>
 3 #include<string>
 4 using namespace std;
 5 
 6 
 7 const int maxn = 500000 + 5;
 8 
 9 int n;
10 int a[maxn],b[maxn];
11 
12 int main()
13 {
14     ios::sync_with_stdio(false);
15     //freopen("D:\txt.txt", "r", stdin);
16     int T;
17     int x;
18     cin >> T;
19     while (T--)
20     {
21         cin >> n;
22         int cnt1 = 0, cnt2 = 0;
23         for (int i = 0; i < n; i++)
24         {
25             cin >> x;
26             if (x>0)   a[cnt1++] = x;
27             else  b[cnt2++] = -x;
28         }
29         sort(a, a + cnt1);
30         sort(b, b + cnt2);
31         int ans = 1;
32         int p1 = 0, p2 = 0;
33         int flag,pre;
34         if (a[0] < b[0])
35         {
36             pre = a[0];
37             flag = 1;
38         }
39         else
40         {
41             pre = b[0];
42             flag = 2;
43         }
44         while (p1 < cnt1 && p2 < cnt2)
45         {
46             if (flag == 1)
47             {
48                 while (p2 < cnt2 && b[p2] <= pre)   p2++;
49                 if (p2 >= cnt2)  break;
50                 pre = b[p2];
51                 ans++;
52                 flag = 2;
53             }
54             else if (flag == 2)
55             {
56                 while (p1 < cnt1 && a[p1] <= pre)   p1++;
57                 if (p1 >= cnt1)  break;
58                 pre = a[p1];
59                 ans++;
60                 flag = 1;
61             }
62         }
63         cout << ans << endl;
64     }
65 }