P1407 工资

题目描述

有一家世界级大企业，他们经过调查，发现了一个奇特的现象，竟然在自己的公司里，有超过一半的雇员，他们的工资完全相同！

公布了这项调查结果后，众多老板对于这一现象很感兴趣，他们发现在自己的公司也存在有这样的现象——超过一半的雇员工资都是x。老板们都很想知道这个x是多少，请你帮忙计算一下。

输入输出格式

输入格式：

输入：(gold.in)

第一行输入一个t，表示有t家公司找你帮忙判断。

之后t行，第i行的第一个数字为Ai表示第i个公司的雇员数，之后Ai个数字表示雇员的工资。

输出格式：

输出：(gold.out)

共输出t行，第i行表示第i个公司的x。（如题意表述）

输入输出样例

输入样例#1：复制

2

5 0 2 0 2 2

4 2 3 3 3

输出样例#1：复制

2

3

说明

数据范围：

t<=10，且员工的资产是10^9以内的非负整数。

70%数据满足Ai<=1000

100% 数据满足Ai<=1000000内存限制 1MB

思路：因为我们要求的数的出现次数大于一半，所以可以用now记录当前的数，用sum记录这个数出现的次数。

如果输入的数和now不同，就可以抵消掉一个sum，反之sum++。最后剩下的一定是我们要求的数。

#include<map>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

map<int,int>ma;

int n,m,num,flag;

int main(){

    scanf("%d",&n);

    while(n--){

        scanf("%d",&m);flag=;

        for(int i=;i<=m;i++){

            scanf("%d",&num);

            ma[num]++;

            if(ma[num]>m/&&!flag){

                cout<<num<<endl;

                flag=;

            }

        }

        ma.clear();

    }

}

70分暴力

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,m,flag;

int main(){

    scanf("%d",&n);

    while(n--){

        scanf("%d",&m);

        int num,now,sum=;

        for(int i=;i<=m;i++){

            scanf("%d",&num);

            if(num==now)    sum++;

            else{

                if(sum<=){ sum=;now=num; }

                else sum--;

            }

        }

        cout<<now<<endl;

    }

}

巴特西

洛谷 P1407 工资

P1407 工资

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章