Hduoj1029-Ignatius and the Princess IV-(dp)

发布于 2019-07-27  527 次阅读


问题传送门:

题意:

给你n个数字,请你找出出现至少(n+1)/2次的数字。
多组输入,n最大是1e6.

分析:

动态规划的思想。
因为要求数个数过半,所以如果存在,必只有一个。
若 a 为n个数中出现次数过半的数,则去掉2k个数,当这2k个数不存在出现次数超过k的数时,剩余n-2k个数中出现次数过半的数仍是a。
这还是容易理解的,我们就假设最差的情况去掉的2k个数中有 k  个 a , 那同时也去掉了k个
其它的数。所以剩下的数中 出现次数过半的数仍是a。
所以,定义两个变量分别为ans、cnt。
ans记录当前出现次数过半的数,cnt记录它出现的次数。
当下一个数等于ans时,cnt++;
当下一个数不等于ans时,cnt--;
当cnt = 0时,说明 当前的 ans 在前2k个数中出现次数不过半,即可不考虑这2k个数。
将ans 赋值为下一个新数,cnt赋值为1,重复上一个步骤。

代码:

#include <iostream>

using namespace std;

int main()
{
    int n, ans, cnt, t;
    while(cin >> n)
    {
        cnt = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> t;
            if (cnt == 0)
                ans=t, cnt++;
            else
            {
                if(ans==t) cnt++;
                else       cnt--;
            }     
        }
        cout << ans << endl;
    }
    return 0;
}

Simple And Clear