首页 > 代码库 > 编程之美2.3： 寻找发帖水王

编程之美2.3： 寻找发帖水王

2024-07-18 01:17:01   222人阅读

题目：传说，Tango有一大“水王”，他不但喜欢发帖，还会回复其他ID发的帖子，发帖数目超过帖子总数的一半，如果你有一个当前论坛上所有帖子的列表，其中帖子作者的ID也在表中，你能快速找到这个传说中的Tango水王吗?
解题思路：由于水王的发帖数目超过一半，当每次删除两个不同ID的帖子时，水王占得帖子数目仍然大于剩下帖子的一半，重复整个过程，将ID列表中的ID总数降低，转化为更小的问题，从而得到最后水王的ID。
#include <iostream>
#include <fstream>
using namespace std;
const int MAX=1000;
int a[MAX];
int main()
{
    int candidate=nTimes=0,id;
    ifstream Input("data1.txt");
    if(!Input)
    {
        cerr<<"open file error"<<endl;
        exit(1);
    }
    while(!Input.eof())
    {
        Input>>id;
        if(nTimes==0)
        {
           candidate=id;
           nTimes++;
        }
        else
        {
            if(candidate==id)
                nTimes++;
            else
                nTimes--;
        }
    }
    cout<<candidate<<endl;
   
} 
问题扩展：如果没有超级水王了，可是有三个ID在列表中出现的次数都超过了1/4，怎么找出这三个ID？
解题思路：现在问题是有三个水王，每次删除4个ID不同的帖子，不影响三个水王在剩余ID中出现仍然超过1/4，故可以每次删除4个不同的ID，直到剩下3个ID为止。
<span style="font-size:18px;">#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;

int main(int argc,char *argv[]){
	int candidate[3]={0,0,0},nTimes[3]={0,0,0},id;
	ifstream Infile("data.txt");
	if(!Infile)
	{
		cerr<<"Open file error!"<<endl;
		exit(1);
	}
	while(!Infile.eof())
	{
		Infile>>id;
		if(nTimes[0]==0)
		{
			candidate[0]=id;
			nTimes[0]++;
		}
		else if(nTimes[1]==0)
		{
			candidate[1]=id;
			nTimes[1]++;
		}
		else if(nTimes[2]==0)
		{
			candidate[2]=id;
			nTimes[2]++;
		}
		else
		{
			if(candidate[0]==id)
				nTimes[0]++;
			else if(candidate[1]==id)
				nTimes[1]++;
			else if(candidate[2]==id)
				nTimes[2]++;
			else
			{
				nTimes[0]--;
				nTimes[1]--;
				nTimes[2]--;
			}
		}
	}
	cout<<candidate[0]<<" "<<candidate[1]<<" "<<candidate[2]<<endl;
	return 0;
}</span>

参考文章：http://blog.csdn.net/super_chris/article/details/7187376
ps:由于作者技术水平有限，如有错误和不恰当之处，还望读者不吝赐教！






























        

            
                
                  
                
                

                    联系

                    我们