Jessica's a very lovely girl wooed by lots of boys. Recently she has a problem. The final exam is coming, yet she has spent little time on it. If she wants to pass it, she has to master all ideas included in a very thick text book. The author of that text book, like other authors, is extremely fussy about the ideas, thus some ideas are covered more than once. Jessica think if she managed to read each idea at least once, she can pass the exam. She decides to read only one contiguous part of the book which contains all ideas covered by the entire book. And of course, the sub-book should be as thin as possible.
A very hard-working boy had manually indexed for her each page of Jessica's text-book with what idea each page is about and thus made a big progress for his courtship. Here you come in to save your skin: given the index, help Jessica decide which contiguous part she should read. For convenience, each idea has been coded with an ID, which is a non-negative integer.
Input
The first line of input is an integer P (1 ≤ P ≤ 1000000), which is the number of pages of Jessica's text-book. The second line contains P non-negative integers describing what idea each page is about. The first integer is what the first page is about, the second integer is what the second page is about, and so on. You may assume all integers that appear can fit well in the signed 32-bit integer type.
Output
Output one line: the number of pages of the shortest contiguous part of the book which contains all ideals covered in the book.
Sample Input
5
1 8 8 8 1
Sample Output
2
题意:
一本书有p页 每一页都有一个知识点ai 存在不同两页上的知识点相同的情况
求最少读连续的多少页书 能把所有的知识点全部覆盖到
尺取法:
反复的推进区间的开头和结尾 来求满足条件的最小区间的方法被称为尺取法
尺取法的复杂度为O(n).
题解:
初始化 start end sum =0;
然后推进end 直到恰好满足条件退出 如果区间已经到了结尾 仍不满足 则退出
然后更新答案 ans = min(ans,end-start);
然后start推进一位,要处理这时对sum的影响
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#include <queue>
using namespace std;
#define lowbit(x) (x&(-x))
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.141592653589793238462
#define INF 0x3f3f3f3f3f
#define mem(a) (memset(a,0,sizeof(a)))
typedef long long ll;
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
const int N=1e6+;
const int mod=1e9+;
int a[N];
int main()
{
int n;
while(~scanf("%d",&n)){
map<int,int>mp;
int num=;
for(int i=;i<n;i++){
scanf("%d",a+i);
if(!mp[a[i]]) num++;
mp[a[i]]++;
}
int st=,t=,sum=,ans=n;
mp.clear();
while(){
while(t<n&&sum<num){
if(!mp[a[t++]]++)
sum++;
}
if(sum<num) break;
ans = min(ans,t-st);
if(--mp[a[st++]]==)
sum--;
}
printf("%d\n",ans);
}
return ;
}
POJ 3320 Jessica's Reading Problem (尺取法)的更多相关文章
-
POJ 3320 Jessica&#39;s Reading Problem 尺取法/map
Jessica's Reading Problem Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 7467 Accept ...
-
POJ 3320 Jessica&#39;s Reading Problem 尺取法
Description Jessica's a very lovely girl wooed by lots of boys. Recently she has a problem. The fina ...
-
poj 3320 jessica&#39;s Reading PJroblem 尺取法 -map和set的使用
jessica's Reading PJroblem Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 9134 Accep ...
-
尺取法 POJ 3320 Jessica&#39;s Reading Problem
题目传送门 /* 尺取法:先求出不同知识点的总个数tot,然后以获得知识点的个数作为界限, 更新最小值 */ #include <cstdio> #include <cmath> ...
-
POJ 3061 Subsequence 尺取法 POJ 3320 Jessica's Reading Problem map+set+尺取法
Subsequence Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 13955 Accepted: 5896 Desc ...
-
POJ 3320 Jessica&#39;s Reading Problem
Jessica's Reading Problem Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 6001 Accept ...
-
POJ 3320 Jessica‘s Reading Problem(哈希、尺取法)
http://poj.org/problem?id=3320 题意:给出一串数字,要求包含所有数字的最短长度. 思路: 哈希一直不是很会用,这道题也是参考了别人的代码,想了很久. #include&l ...
-
题解报告:poj 3320 Jessica&#39;s Reading Problem(尺取法)
Description Jessica's a very lovely girl wooed by lots of boys. Recently she has a problem. The fina ...
-
poj3061 Subsequence&;&;poj3320 Jessica&#39;s Reading Problem(尺取法)
这两道题都是用的尺取法.尺取法是<挑战程序设计竞赛>里讲的一种常用技巧. 就是O(n)的扫一遍数组,扫完了答案也就出来了,这过程中要求问题具有这样的性质:头指针向前走(s++)以后,尾指针 ...
随机推荐
-
(32)odoo中的编码问题
对于全部是英文就不存在问题,但我们常用中文,这样会导致一个棘手的问题 约定: 系统Ubuntu trusty14.04 自带python2.7.6 python2.7.9 自己升级了 升级方法: -- ...
-
Sublime Text博客插件 --- iblog
iblog是一款 sublime 博客插件,目前只支持cnblog. 项目地址:https://github.com/iskeeter/iblog 功能介绍 新建和更新cnblog的博客 支持mark ...
-
Win32中GDI+应用(五)--GDI与GDI+编程模型的区别
在GDI里面,你要想开始自己的绘图工作,必须先获取一个device context handle,然后把这个handle作为绘图复方法的一个参数,才能完成任务.同时,device context ha ...
-
MySQL 存储过程和函数(转)
概述 一提到存储过程可能就会引出另一个话题就是存储过程的优缺点,这里也不做讨论,一般别人问我我就这样回答你觉得它好你就用它.因为mysql中存储过程和函数的语法非常接近所以就放在一起,主要区别就是函数 ...
-
编写JQuery插件-3
该了解我们也知道的差不多了,接下来编写我们第一个jq插件吧 封装对象方法的插件 我们编写一个设置和获取颜色的插件,我们需要实现两个功能 1.设置匹配元素的颜色 2.获取匹配元素(元素集合的第一个)的颜 ...
-
Go笔记-结构、类型、常量
[类型] 1.可以包含数据的变量(或常量),可以使用不同的数据类型或类型来保存数据.使用 var 声明的变量的值会自动初始化为该类型的零值.类型定义了某个变量的值的集合与可对其进行操作的集合. 2 ...
-
springboot springmvc拦截器 拦截POST、PUT、DELETE请求参数和响应数据,并记录操作日志
1.操作日志实体类 @Document(collection = "operation_log") @Getter @Setter @ToString public class O ...
-
全志A33移植LCD驱动(ILI9806E)
0x00 环境说明: 所使用的开发板为锐尔威视的插针版A33_Vstar 屏幕是买的第三方的KD050FWFPA011-C009A,其中LCD驱动IC为ILI9806E,所使用的接口为RGB666 0 ...
-
关于LinQ中“from";前置的原因
原文地址:http://blog.csdn.net/yuzifen/article/details/6754003 概括来说是:为了IDE的智能感知(Intelisence)功能,(或说为了进行类型推 ...
-
centos 6.5 gogs迁移外部仓库报错
安装gogs git软件后,使用迁移外部仓库功能,提示“你没有获得导入本地仓库的权限”,发现是因为使用的ssh的链接进行导入 目前gogs咱不支持,随后使用github的https链接导入,依然报错 ...