一 题目
#include<iostream> using namespace std; int curId=0;//当前灌水id int idNum=0;//当前灌水id的数量 void deal(int arr[],int n) { for (int i=0;i<n;i++) { if (idNum==0) //当前灌水的id数量变为0或者抵消成为了0 { idNum++;//灌水帖子数量+1 curId=arr[i];//用curId记录当前灌水Id } else { if(curId==arr[i])//如果新的灌水帖子与当前帖子Id相同则Id数量+1 idNum++; else //如果不同,则抵消一个当前Id idNum--; } } } void main() { int i; int count=0;//记录水王的帖子数量 int n;//灌水帖子数 int * arr=new int[n]; cout<<"请输入灌水帖子数:"; cin>>n; cout<<"输入每个灌水帖子id:"<<endl; for(i=0;i<n;i++) { cin>>arr[i]; } deal(arr,n); for(i=0;i<n;i++) { if(arr[i]==curId) { count++; } } cout<<"\"水王\"Id是:"; cout<<curId<<endl; cout<<"水贴数量为:"; cout<<count<<endl; }
四 程序截图
五 实验总结
本次实验采用的算法复杂度为o(n),采用了抵消的方法,较为有趣,主要是利用了水王灌水超过总帖子一半的漏洞,极大的简化了算法。
原文:http://www.cnblogs.com/tianma-0/p/4445181.html