UVa 11039 - Building designing

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

分析：按照绝对值大小排一次序，然后扫描一次，顺便做个标记即可。

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

int cmp(int a,int b)
{
return abs(a)<abs(b);
}
int main()
{
int cas,a[100000],n;
scanf("%d",&cas);
for(int ii=1;ii<=cas;ii++)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n,cmp);
int flag=0;
int ans=0;
for(int i=1;i<=n;i++)
{
if(flag==0)
{
if(a[i]>0)
flag=1;
else
flag=2;
ans++;
}
else if(flag==1)
{
if(a[i]<0)
{
flag=2;
ans++;
}
}
else if(flag==2)
{
if(a[i]>0)
{
flag=1;
ans++;
}
}
}
printf("%d\n",ans);
}
return 0;
}

巴特西

UVa 11039 - Building designing

最新文章

热门文章