首页 kuangbin带你飞

题目描述

"OK, you are not too bad, em... But you can never pass the next test." feng5166 says.

"I will tell you an odd number N, and then N integers. There will be a special integer among them, you have to tell me which integer is the special one after I tell you all the integers." feng5166 says.

"But what is the characteristic of the special integer?" Ignatius asks.

"The integer will appear at least (N+1)/2 times. If you can't find the right integer, I will kill the Princess, and you will be my dinner, too. Hahahaha....." feng5166 says.

Can you find the special integer for Ignatius?

输入描述:

The input contains several test cases. Each test case contains two lines. The first line consists of an odd integer N(1<=N<=999999) which indicate the number of the integers feng5166 will tell our hero. The second line contains the N integers. The input is terminated by the end of file.

输出描述:

For each test case, you have to output only one line which contains the special number you have found.

输入样例:

5
1 3 2 3 3
11
1 1 1 1 1 5 5 5 5 5 5
7
1 1 1 1 1 1 1

输出样例:

3
5
1
ac代码(纯净源码)

注意:vjudge不支持万能头文件

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iomanip>
#include <complex>
#include <cassert>
#include <sstream>
#include <fstream>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <valarray>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int N;
    while (scanf("%d", &N) != EOF) {
        int cnt = 0;
        int num;
        for (int i = 0; i < N; ++i) {
            int nus;
            cin >> nus;
            if (cnt == 0) {
                num = nus;
                cnt++;
            } else {
                if (num == nus) {
                    cnt++;
                } else {
                    cnt--;
                }
            }
        }
        cout << num << endl;
    }
    return 0;
}
心得:

本题的大意就是给几个数(一个奇数个),让你找到这几个数里面出现次数最多的那个,主要条件是出现次数最多的那个出现次数大于一半。

所以思路是什么呢:如果他出现次数超过一半了,那么就算每一个这个数和另一个不同的数消除,最后剩下的肯定还是那个最多的数就比如:

3 2 3 4 3

3和2相消,3和4相消,最后剩下的还是3

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int N;
    while (scanf("%d", &N) != EOF) {
        int cnt = 0;
        int num;
        for (int i = 0; i < N; ++i) {
            int nus;
            cin >> nus;
            if (cnt == 0) {
                num = nus;
                cnt++;
            } else {
                if (num == nus) {
                    cnt++;
                } else {
                    cnt--;
                }
            }
        }
        cout << num << endl;
    }
    return 0;
}

https://vjudge.net/problem/HDU-1029




文章评论

目录