Greedy:Jessica's Reading Problem(POJ 3320)

时间:2022-09-23 21:11:42

                Greedy:Jessica's Reading Problem(POJ 3320)

            Jessica's Reading Problem

  题目大意:Jessica期末考试临时抱佛脚想读一本书把知识点掌握,但是知识点很多,而且很多都是重复的,她想读最少的连续的页数把知识点全部掌握(知识点都在书上,每一页都是一个知识点)

  这一题可以用3061的游标卡尺法,我们可以先数数书上倒到底有多少个知识点,因为知识点都是序数,我们可以用二分法直接找到O(PlogP),这里可以采用set模板直接偷懒了,然后我们就可以用游标卡尺法了,因为所有知识点都要出现一次,所以我们统计新的知识点的出现就好了,最后我们找最短的那个连续就好。

  

 #include <iostream>
#include <functional>
#include <algorithm>
#include <map>
#include <set> using namespace std; static int books[]; void solve(const int); int main(void)
{
int pages;
while (~scanf("%d", &pages))
{
for (int i = ; i < pages; i++)
scanf("%d", &books[i]);
solve(pages);
}
return ;
} void solve(const int pages)
{
int ideas_size, s = , t = , ans, nums = ;//游标卡尺法标准形式
static set<int>ideas;
static map<int, int>index;//把ideas和index放函数里面初始化能省几十ms for (int i = ; i < pages; i++)
ideas.insert(books[i]);
ideas_size = ideas.size();
ans = pages;//ans千万不要初始化成答案个数了,之前在这里初始化错了导致wa while ()
{
while (t < pages && nums < ideas_size)
{
if (index[books[t++]]++ == )//找不到这个元素,则一定在尾端
nums++;
}
if (nums < ideas_size)//因为知识点的个数一定是符合条件的,所以这里直接作为跳出条件就可以了
break;
ans = min(ans, t - s);
if (--index[books[s++]] == )
nums--;
}
printf("%d\n", ans);
}

  Greedy:Jessica's Reading Problem(POJ 3320)

  因为使用模板的,所以速度会慢一点

Greedy:Jessica's Reading Problem(POJ 3320)的更多相关文章

  1. A - Jessica&&num;39&semi;s Reading Problem POJ - 3320 尺取

    A - Jessica's Reading Problem POJ - 3320 Jessica's a very lovely girl wooed by lots of boys. Recentl ...

  2. Jessica&&num;39&semi;s Reading Problem POJ - 3320

    Jessica's Reading Problem Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 17562   Accep ...

  3. Jessica&&num;39&semi;s Reading Problem POJ - 3320(尺取法2)

    题意:n页书,然后n个数表示各个知识点ai,然后,输出最小覆盖的页数. #include<iostream> #include<cstdio> #include<set& ...

  4. 尺取法 POJ 3320 Jessica&&num;39&semi;s Reading Problem

    题目传送门 /* 尺取法:先求出不同知识点的总个数tot,然后以获得知识点的个数作为界限, 更新最小值 */ #include <cstdio> #include <cmath&gt ...

  5. POJ 3320 Jessica&&num;39&semi;s Reading Problem

    Jessica's Reading Problem Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 6001   Accept ...

  6. POJ 3061 Subsequence 尺取法 POJ 3320 Jessica's Reading Problem map&plus;set&plus;尺取法

    Subsequence Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 13955   Accepted: 5896 Desc ...

  7. POJ 3320 Jessica&&num;39&semi;s Reading Problem 尺取法&sol;map

    Jessica's Reading Problem Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 7467   Accept ...

  8. POJ 3220 Jessica&&num;39&semi;s Reading Problem

    Jessica's Reading Problem Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 12944   Accep ...

  9. POJ3320 Jessica&&num;39&semi;s Reading Problem 2017-05-25 19&colon;55 38人阅读 评论&lpar;0&rpar; 收藏

    Jessica's Reading Problem Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 12346   Accep ...

随机推荐

  1. Android 网络状态检测

    package com.example.administrator.yunstore.net; import android.app.AlertDialog; import android.conte ...

  2. IComparable&lt&semi;T&gt&semi; Vs&period; IComparer&lt&semi;T&gt&semi; System&period;Comparison&lt&semi;T&gt&semi;

    Well they are not quite the same thing as IComparer<T> is implemented on a type that is capabl ...

  3. AOP 学习

    学习 Spring.Net 的AOP 的时候,在做一个简单的测试例子的时候,配置文件和代码逻辑都是没问题的,但始终报这样一个异常: 无法将类型为“CompositionAopProxy_1e76f37 ...

  4. Linux Shell系列教程之(十二)Shell until循环

    本文是Linux Shell系列教程的第(十二)篇,更多Linux Shell教程请看:Linux Shell系列教程 在上两篇文章Linux Shell系列教程之(十)Shell for循环和Lin ...

  5. 13&period;python笔记之pyyaml模块

    Date:2016-03-25 Title:13.Python笔记之Pyymal模块使用 Tags:Python Category:Python 博客地址:www.liuyao.me 作者:刘耀 YA ...

  6. Masonry1&period;0&period;2 源码解析

    在了解Masonry框架之前,有必要先了解一下自动布局的概念.在iOS6之前,UI布局的方式是通过frame属性和Autoresizing来完成的,而在iOS6之后,苹果公司推出了AutoLayout ...

  7. 使用nodeValue获取值与a标签默认跳转的冲突问题

    今天看javascript DOM编程艺术(第2版)发现这样一个例子: 效果图: 完整代码: <!DOCTYPE html> <html lang="en"&gt ...

  8. firewall端口放行

    添加 sudo firewall-cmd --zone=public --add-port=10050/tcp --permanent sudo firewall-cmd --add-port=929 ...

  9. JDK动态代理和CGLIB代理的区别

    一.原理区别: java动态代理是利用反射机制生成一个实现代理接口的匿名类,在调用具体方法前调用InvokeHandler来处理. 而cglib动态代理是利用asm开源包,对代理对象类的class文件 ...

  10. centos5&amp&semi;6的启动过程

    CentOS-6系统启动过程: 按下开关按钮 给服务器供电 BIOS自检操作     检查硬件是否存在异常(显示logo画面) MBR引导系统      硬盘启动系统  光驱启动系统  U盘启动系统  ...