首页 > ACM题库 > HDU-杭电 > hdu 2192 MagicBuilding[解题报告]C++
2013
12-30

hdu 2192 MagicBuilding[解题报告]C++

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

点击打开链接

/*

题目有点水,单自己犯二了,只需要看哪个数最多就行了,然狗输出那个数,自己刚开始没有结构体,定义两个数组,一个存数据,一个数组用来标记,但是这里是不能用数组标记的,因为数据范围的int的,可能是10万。。。

*/

#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;
}

解题转自:http://blog.csdn.net/yangyafeiac/article/details/8826861


  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;

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法