转载请注明文本链接 http://blog.csdn.net/yangnanhai93/article/details/40441709

题目链接地址：http://ac.jobdu.com/problem.php?pid=1380

第一次这么正式的去写这个ACM的算法的博客，感觉这个题目给我的触动有点大，非常多时候很多其它的算法须要观察，须要细心的品味题目，才可以有：“啊哈，算法”——《编程珠玑》

先说下自己的惯性思路吧，由于这个题目就是非常明显一个统计的问题，所以，我一上来的就是尽量的去降低内存开销，所以我採用的是：

在我看来这个应该是没有问题的，由于int 4字节 char 1字节，由于m%n！=0，且n>=2，所以这个map的元素中的个数是小于等于5*5*10^5=2.5M的，然后我把代码精简，希望得到更小的开销，可是发现和使用int short作为map的开销是一样的，这个不能理解。

#include <stdio.h>

#include <map>

using namespace std;

int main()

{

    map<int,char> mp;

    map<int,char>::iterator key;

    int n,m,num;

    while(scanf("%d%d",&n,&m)!= EOF)

    {

        mp.clear();

        while(m--)

        {

            scanf("%d",&num);

            key = mp.find(num);

            if(key == mp.end())

                mp.insert(pair<int,char>(num,'1'));

            else if(key->second<(n+'0'))

                key->second++;

        }

        key=mp.begin();

        while(key!=mp.end()&&key->second==(n+'0'))

            key++;

        printf("%d\n",key->first);

    }

    return 0;

}

/**************************************************************

    Problem: 1380

    User: vincent_ynh

    Language: C++

    Result: Memory Limit Exceed

****************************************************************/

第二个略微能够降低空间的思路是，发现仅仅须要4位存储就能够了，然后用位去存储，这里，由于我个人的理解题目失误，误觉得是1-10^6个数，然后写了一个用位存储的代码，非常少写位操作的代码，写得比較难看，可是觉得作为一个精益求精的coder还是须要很多其它的使用的，《编程珠玑》中的第一个电话本的样例给我的触动特别大，让我感受到代码原来能够如此的巧妙，好吧，扯远了，这里贴一下，假设数据的范围小的时候，也能够使用例如以下位存储代码：

#include <stdio.h>

#include <memory.h>

int main()

{

    int A[300000],B[2]={15,240};

    int n,m,num;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        memset(A,0,sizeof(A));

        while(m--)

        {

            scanf("%d",&num);

            int tmp=(num-1)/2;

            int x=(num-1)%2;

            if((A[tmp]&B[x])>>(4*x)<=n)

            {

                A[tmp]=A[tmp]+(1<<(4*x));

            }

        }

        for(int i=1;;i++)

        {

            int tmp=(i-1)/2;

            int x=(i-1)%2;

            if(((A[tmp]&B[x])>>(4*x))%n!=0)

            {

                printf("%d\n",i);

                break;

            }

        }

    }

    return 0;

}

/**************************************************************

    Problem: 1380

    User: vincent_ynh

    Language: C++

    Result: Runtime Error

****************************************************************/

最后就是该题我能想到的眼下最优的算法了：

我们对每个数进行二进制编码，得到的是32 位的数，假设这个数出现了n次，那么这种编码就应该出现了n次，假设对n取余，那么恰好就把这些出现n次的数消除了。想通了这个，然后接下来就是没有出现n次的，那么就是出现了m%n次的，当然能够是m%n+x*n，不影响的，在剩余的数组中，就剩下了lucky number的编码（每 位乘以m%n），所以，我们仅仅须要把数组中对每一位取余（%n）同一时候，把非0位，改为1,位不变，最后把该数组转换成整数就能够了。

代码的主要思路我们通过样例可以发现：

2 5

1 1 2 2 3

结果是3

编码得到00000001 00000001 00000010 00000010 00000011（由于数字比較小，省略了前面3位即24个0）

整合进数组之后00000033 取余之后为00000011

然后把非0的转换为1，得到00000011

把数组转换为整数为3，所以结果为3

这里补充一下“位与(&)”操作，位与(&)操作是对数字进行二进制编码，相应位假设同为1，则为1，否则为0

实际代码例如以下：

#include <stdio.h>

#include <memory.h>

int main()

{

    int A[32],m,n,num;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        memset(A,0,sizeof(A));

        for(int j=0;j<m;j++)

        {

            scanf("%d",&num);

            for(int i=0;i<32;i++)

            {

                A[i]=A[i]+(num&1);

                A[i]=A[i]%n;

                num=num>>1;

            }

        }

        int tmp=m%n,result=0;

        for(int i=0;i<32;i++)

        {

            if(A[i]%n==tmp)

                result+=1<<i;

        }

        printf("%d\n",result);

    }

    return 0;

}

/**************************************************************

    Problem: 1380

    User: vincent_ynh

    Language: C++

    Result: Accepted

    Time:1620 ms

    Memory:1020 kb

****************************************************************/

欢迎不论什么想学习算法的人交流：vincent_ynh@163.com