洛谷P1407 工资

洛谷P1407 工资

本题地址:http://www.luogu.org/problem/show?pid=1407

题目描述

有一家世界级大企业,他们经过调查,发现了一个奇特的现象,竟然在自己的公司里,有超过一半的雇员,他们的工资完全相同!
公布了这项调查结果后,众多老板对于这一现象很感兴趣,他们发现在自己的公司也存在有这样的现象——超过一半的雇员工资都是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

【思路】

因为有内存限制所以用map会爆内存。

这个题目的突破口在于求的是出现次数超过一半的数字x(而非飞翔同学说的求众数),所以x一定会有连续,我们只需要求出连续长度最长的数字即可。

【代码】

 #include<iostream>
#include<map>
using namespace std; int n; int main() {
ios::sync_with_stdio(false);
int T; cin>>T;
while(T--) {
int x,a=,A;
cin>>A;
bool f=false;
for(int i=;i<A;i++) {
int u; cin>>u;
if(a==) x=u;
if(x==u) a++; else a--;
}
cout<<x<<"\n";
}
return ;
}
上一篇:背水一战 Windows 10 (65) - 控件(WebView): 对 WebView 中的内容截图, 通过 Share Contract 分享 WebView 中的被选中的内容


下一篇:ios学习笔记图片+图片解释(c语言 oc语言 ios控件 ios小项目 ios小功能 swift都有而且笔记完整喔)