2013
12-30

# MagicBuilding

As the increase of population, the living space for people is becoming smaller and smaller. In MagicStar the problem is much worse. Dr. Mathematica is trying to save land by clustering buildings and then we call the set of buildings MagicBuilding. Now we can treat the buildings as a square of size d, and the height doesn’t matter. Buildings of d1,d2,d3….dn can be clustered into one MagicBuilding if they satisfy di != dj(i != j).
Given a series of buildings size , you need to calculate the minimal numbers of MagicBuildings that can be made. Note that one building can also be considered as a MagicBuilding.
Suppose there are five buildings : 1, 2, 2, 3, 3. We make three MagicBuildings (1,3), (2,3), (2) .And we can also make two MagicBuilding :(1,2,3), (2,3). There is at least two MagicBuildings obviously.

The first line of the input is a single number t, indicating the number of test cases.
Each test case starts by n (1≤n≤10^4) in a line indicating the number of buildings. Next n positive numbers (less than 2^31) will be the size of the buildings.

The first line of the input is a single number t, indicating the number of test cases.
Each test case starts by n (1≤n≤10^4) in a line indicating the number of buildings. Next n positive numbers (less than 2^31) will be the size of the buildings.

2
1
2
5
1 2 2 3 3

1
2

/*

*/

#include"stdio.h"
#include"string.h"
struct node
{
int t;
int n;
}A[10001];
int main()
{
int T;
int n;
int cnt;
int i,a;
int j,k;
scanf("%d",&T);
while(T--)
{
memset(A,0,sizeof(A));
k=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a);
for(j=0;j<k;j++)
{
if(A[j].n==a)
{
A[j].t++;break;
}
}
if(j==k)
{
A[k].n=a;
A[k].t++;
k++;
}
}
int ans;
ans=0;
for(i=0;i<k;i++)
{
if(ans<A[i].t)
ans=A[i].t;
}
printf("%d\n",ans);
}
return 0;
}

1. int half(int *array,int len,int key)
{
int l=0,r=len;
while(l<r)
{
int m=(l+r)>>1;
if(key>array )l=m+1;
else if(key<array )r=m;
else return m;
}
return -1;
}
这种就能避免一些Bug
l,m,r
左边是l,m;右边就是m+1,r;