Question

求杭电ACM 1029解释

http://acm.hdu.edu.cn/showproblem.php?pid=1029
#include<stdio.h>
int main()
{
int n,ans,temp,c;
while(scanf("%d",&n)!=EOF&&n)
{
scanf("%d",&ans),c=1;
for(int i=2;i<=n;++i)
{
scanf("%d",&temp);
c+=(temp==ans?1:-1);
if(!c)
scanf("%d",&ans),++i,c=1;
}
printf("%d\n",ans);
}return 0;
}
这是我在百度上找到的代码，但是我看不明白，希望各位高手帮我解释一下代码的意思，如果有更好的方法更是感激不尽

Answer 1

代码这样写的关键就是要找的那个数的数目大于一半,所以即使这个数与其它所有的数进行抵消,最后剩的还是它(因为数的总数为奇数,且这个数大于一半),何况其它数之间也会造成消耗,所以代码这样写,得到的ans一定就是所求.

提供一个其它的解法,代码比这个简单一些且容易理解,不过map不知道你会不会用(还没学到的话自学一下,很简单的)

#include <iostream>
#include <map>
using namespace std;

int main()
{
int n,d,ans;
while(cin>>n)
{
map<int,int> m;
for(int i=1;i<=n;i++)
{
scanf("%d",&d);
m[d]++;
if(m[d]==(n+1)/2)
ans=d;
}
printf("%d\n",ans);
}
return 1;
}

Answer 2

解释下这个算法:

1. 题目大意: 一组数中某个数出现次数达到一半以上, 要你找出这个数. 这是废话.

2. 由于n很大, 估计连nlogn都会卡掉, 所以必定是线性算法. 也是废话.

3. 假设我们随意的 成对(别看漏) 划掉数组中的数, 前提是, 划掉的两个数不同. 则不管你怎么划, 最后能剩下的, 一定是那个特殊的数. 这个仔细想, 是关键.

4. 因此得到以下算法:
读入数a, 再读b.
如b==a, count_a++, 否则, count_a--(即, 成对划掉a与b), 如果count_a==0, 舍掉a, 再找个.
反正就是划划划. 划到最后剩下的就是答案了. (n为奇数, 保证了最后一定有剩的)
简单吧?

Answer 3

方法：
1.读取一个数ans，用c来计数，初始时c为1。
2.接下来读数，如果与ans相同，则c加1；否则c减1。
3.当c为0时，重新读取一个数作为ans,c=1。重复上述步骤。

原理：
要找的数设为a。读到相同的数时，c加1，相当于多了一个。读到不同的数时，c-1，相当于抵消了一个。既然a的个数在一半以上，即使其它数全与a抵消，a也会剩余。更何况读到的ans不是a时，其它数的个数会相互抵消。所以，a至多会出现中途个数为0的情况，但到最后的那个ans肯定为a。