uva 11039

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

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 
 7 int a[500010];
 8 int n;
 9 
10 int cmp(int a,int b)
11 {
12     return abs(a)<abs(b);
13 }
14 
15 int main()
16 {
17     int t;
18     scanf("%d",&t);
19     while(t--)
20     {
21         scanf("%d",&n);
22         for(int i=0;i<n;++i)
23             scanf("%d",&a[i]);
24       sort(a,a+n,cmp);
25     int cnt=0;
26     int flag=0;
27     for(int i=0;i<n;++i)
28     {
29         if(flag==0)
30         {
31             if(a[i]>0)
32                 flag=1;
33             else
34               flag=2;
35             cnt++;
36         }
37         else if(flag==1)
38         {
39             if(a[i]<0)
40             {
41                 flag=2;
42                 cnt++;
43             }
44         }
45         else if(flag==2)
46         {
47             if(a[i]>0)
48             {
49                 flag=1;
50                 cnt++;
51             }
52         }
53     }
54     printf("%d
", cnt);
55     }
56     return 0;
57 }