Codeforces 558B 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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
using namespace std; const double PI = acos(-1.0);
const double e = 2.718281828459;
const double eps = 1e-8; struct node
{
int num;
int time;
int l;
int r;
int range;
} index[1000010]; int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int n;
while(cin>>n)
{
map<int, int>g;
g.clear();
memset(index, 0, sizeof(index));
int t;
int d = 0;
int dd;
int maxd = 1;
int maxtime = 0;
int maxrange = 1;
for(int i = 1; i <= n; i++)
{
scanf("%d", &t);
if(g[t] != 0)
{
dd = g[t];
index[dd].time++;
index[dd].r = i;
index[dd].range = index[dd].r-index[dd].l+1;
if(maxtime<index[dd].time || maxtime==index[dd].time&&maxrange>index[dd].range)
{
maxtime = index[dd].time;
maxd = dd;
maxrange = index[dd].range;
}
}
else
{
g[t] = ++d;
dd = g[t];
index[dd].num = t;
index[dd].time = 1;
index[dd].l = index[dd].r = i;
index[dd].range = 1;
if(maxtime < index[dd].time)
{
maxtime = index[dd].time;
maxd = dd;
maxrange = 1;
}
}
}
printf("%d %d\n", index[maxd].l, index[maxd].r);
}
return 0;
}
最新文章
- Windows XP系统下添加任务计划常出现问题解决办法
- 介绍一个非常好用的跨平台C++开源框架:openFrameworks
- 微信在IOS7下无法分享图片
- grep笔记
- supervisor(三)xml_rpc
- 关于ORACLE隐式转换后性能问题
- 【转】转换到 COFF 期间失败: 文件无效或损坏
- JAVA 循环在一个数字前面填充0.小例子
- 利用Socket与硬件通信(智能家居)
- 网卡驱动引起openstack的mtu问题
- 深度解读GoogleNet之Inception V1
- CSS透明opacity和IE各版本透明度滤镜filter的准确用法
- java集合遍历的几种方式总结及比较
- java使用jxl,poi解析excel文件
- AI学习---特征工程【特征抽取、特征预处理、特征降维】
- Python-生成器_36
- (1)Phonics自然拼读 英语动画 Fun with Phonics 国际主流英语教学法
- []转帖] 浅谈Linux下的五种I/O模型
- javascript 实现手风琴特效
- idata,xdata,pdata,code