codeforces 558B B. Amr and The Large Array(水题)
题目链接:
1 second
256 megabytes
standard input
standard output
Amr has got a large array of size n. Amr doesn't like large arrays so he intends to make it smaller.
Amr doesn't care about anything in the array except the beauty of it. The beauty of the array is defined to be the maximum number of times that some number occurs in this array. He wants to choose the smallest subsegment of this array such that the beauty of it will be the same as the original array.
Help Amr by choosing the smallest subsegment possible.
The first line contains one number n (1 ≤ n ≤ 105), the size of the array.
The second line contains n integers ai (1 ≤ ai ≤ 106), representing elements of the array.
Output two integers l, r (1 ≤ l ≤ r ≤ n), the beginning and the end of the subsegment chosen respectively.
If there are several possible answers you may output any of them.
5
1 1 2 2 1
1 5
5
1 2 2 3 1
2 3
6
1 2 2 1 1 2
1 5
A subsegment B of an array A from l to r is an array of size r - l + 1 where Bi = Al + i - 1 for all 1 ≤ i ≤ r - l + 1
题意:
使数组的魅力值保持相同,但数组的长度尽量小;
思路:
用vector的大小来看是否对应魅力值的那个数,而vector保存了这个数的各个位置,可以得到长度,一半比较一边更新就好;
AC代码:
/*
2014300227 558B - 9 GNU C++11 Accepted 61 ms 15728 KB
*/
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+;
typedef long long ll;
const double PI=acos(-1.0);
int n,a[N];
vector<int>ve[*N];
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
ve[a[i]].push_back(i);
}
int ans=,l=,r=;
for(int i=;i<=1e6;i++)
{
int g=ve[i].size();
if(g){
if(g>ve[ans].size())
{
int len=g;
l=ve[i][];
r=ve[i][len-];
ans=i;
}
else if(g==ve[ans].size())
{
int s=g;
if(ve[i][s-]-ve[i][]<r-l)
{
l=ve[i][];
r=ve[i][s-];
ans=i;
}
}
}
}
cout<<l<<" "<<r<<endl; return ;
}
最新文章
- GridControl
- ipad横竖屏尺寸(转载)
- Javascript可变长度参数列表 - Arguments对象
- SQL中使用WITH AS提高性能(二)
- Ignoring a Test
- java进制转换器 图形用户界面 十进制及其相反数分别转化为二,四,八,十六进制
- 如何使用JVisualVM进行性能分析
- PAT 7-12 拯救007
- ES 6 系列 - 变量声明
- 360. Sort Transformed Array二元一次方程返回大数序列
- vba 如何去掉返回结果两端的双引号?
- English trip V1 - B 16. Giving Reasons 提供个人信息 Teacher:Lamb Key: Why/Because
- day01_雷神_Python入门
- JavaScript -- Select
- [转]C++之运算符重载(1)
- 引入jQuery
- JavaScript的DOM_操作内容
- MITK 手册
- python基础 实战作业 ---Excel基本读写与数据处理
- 身份证号码正则匹配-javascript