文档章节

[POI2005]SAM-Toy Cars

o
 osc_z1hvg4cu
发布于 2018/04/24 20:10
字数 1262
阅读 7
收藏 0

精选30+云产品,助力企业轻松上云!>>>

洛谷题目链接:[POI2005]SAM-Toy Cars

题目描述

Johnny is a little boy - he is only three years old and enjoys playing with toy cars very much. Johnny has nn different cars. They are kept on a shelf so high, that Johnny cannot reach it by himself. As there is little space in his room, at no moment may there be more than kk toy cars on the floor.

Johnny plays with one of the cars on the floor. Johnny's mother remains in the room with her son all the time. When Johnny wants to play with another car that is on the floor, he reaches it by himself. But when the toy is on the shelf, his mummy has to hand it to him. When she gives Johnny one car, she can at the same time pick any car from the floor and put it back on the shelf (so that there remains sufficient space on the floor).

The mother knows her child very well and therefore can predict perfectly which cars Johnny will want to play with. Having this knowledge, she wants to minimize the number of times she has to hand Johnny a toy from the shelf. Keeping that in mind, she has to put the toys off on the shelf extremely thoughtfully.

TaskWrite a programme that:

reads from the standard input the sequence of toy cars in order in which Johnny will want to play with them,calculates the minimal number of times the mother has to pick cars from the shelf,writes the result to the standard output.

Jasio 是一个三岁的小男孩,他最喜欢玩玩具了,他有n 个不同的玩具,它们都被放在了很高的架子上所以Jasio 拿不到它们. 为了让他的房间有足够的空间,在任何时刻地板上都不会有超过k 个玩具. Jasio 在地板上玩玩具. Jasio'的妈妈则在房间里陪他的儿子. 当Jasio 想玩地板上的其他玩具时,他会自己去拿,如果他想玩的玩具在架子上,他的妈妈则会帮他去拿,当她拿玩具的时候,顺便也会将一个地板上的玩具放上架子使得地板上有足够的空间. 他的妈妈很清楚自己的孩子所以他能够预料到Jasio 想玩些什么玩具. 所以她想尽量的使自己去架子上拿玩具的次数尽量的少,应该怎么安排放玩具的顺序呢?

输入输出格式

输入格式:

In the first line of the standard input there are three integers: $n$ , $k$ , $p$ ( $1\le k\le n\le 100\ 000$ , $1\le p\le 500\ 000$ ), separated by single spaces. These denote respectively: the total number of cars, the number of cars that can remain on the floor at once and the length of the sequence of cars which Johnny will want to play with. Each of the following pp lines contains one integer. These integers are the numbers of cars Johnny will want to play with (the cars are numbered from 1 to $n$ ).

输出格式:

In the first and only line of the standard output one integer should be written - the minimal number of times his mother has to pick a car from the shelf.

输入输出样例

输入样例#1:

3 2 7 1 2 3 1 3 1 2

输出样例#1:

4

简述一下题意: 有n个玩具,要玩p次,每次要玩就要从架子上取,如果地上已经有这个玩具了,就不需要取.每次去架子上取玩具时可以更换一个玩具.现在要求出最少取玩具的次数. </br> 首先来想一下如何才能尽量少的取玩具. 显然,如果一个玩具已经在地上了,就可以不用去取. 但是地上能放的玩具的数量有限,所以我们可以记录每种玩具下一次要被玩的时间next[i],并在需要更换玩具的时候换走当前队列中next[i]最大的那一个玩具.

就拿样例举个栗子吧:

1 2 3 1 3 1 2
  • 首先肯定是要将1,2都放到地板上.
  • 然后要玩3,但是此时地板上并没有3,必须要拿地板上的一个玩具去换3. 这个时候我们就要考虑是换1还是换2了.
  • 显然,如果换走了1,下次又会要玩1,这样很显然是不划算的.所以此时我们取走2,将3拿过来.
  • 接下来几次要玩1,3都可以直接在地上拿.直到最后一次再把2换回来.

所以我们可以得到这样一个贪心策略:要换玩具的时候,换next[i]最远的那个玩具.

然后就是模拟一下入队出队情况,用优先队列维护一下next.

#include<bits/stdc++.h>
using namespace std;
const int N=500000+5;
const int M=100000+5;

int n, k, p;//inqueue times
int a[N], next[N];//next same toy's position
bool vis[M];//the toy is in the queue or not
int ans = 0;

struct cmp{
    bool operator()(const int&x,const int &y){
    return next[x] < next[y];
    }
};

queue <int> q[M];
priority_queue <int,vector<int>,cmp> h;

int gi(){
    int ans = 0, f = 1; char i = getchar();
    while(i<'0'||i>'9'){if(i=='-')f=-1;i=getchar();}
    while(i>='0'&&i<='9'){ans=ans*10+i-'0';i=getchar();}
    return ans * f;
}

int main(){
    //freopen("data.in","r",stdin);
    n = gi(); k = gi(); p = gi();
    for(int i=1;i<=p;i++) a[i] = gi(), q[a[i]].push(i);
    for(int i=1;i<=p;i++){
	    q[a[i]].pop();
	    if(q[a[i]].empty()) next[i] = p+1;
	    else next[i] = q[a[i]].front();
    }
    for(int i=1;i<=p;i++){
	    if(!vis[a[i]]){
	        if(h.size() == k){
		        vis[a[h.top()]] = 0;
		        h.pop();
	        }
	        h.push(i); vis[a[i]] = 1; ans++;
	    }
	    else h.push(i), k++;
    }
    printf("%d\n",ans);
    return 0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

平时使用的Lszrz到底是什么协议?说说Xmodem/Ymodem/Zmodem

XMODEM, YMODEM, and ZMODEM 由于平时使用rz/sz较多,r/s好理解,一个send一个receive。但是由不太清楚z是什么意思,故有此文。 sx/rx, sb/rb (b=batch)和sz/rz分别实现了xmodem,ymodem和z...

独钓渔
41分钟前
17
0
真正的强智能时代已经到来。道翰天琼认知智能机器人平台API大脑。

最近,我常说人工智能的寒冬快要来了,提醒业界要做好思想准备,但同时我也说:冬天来了,春天就不会远了…… 2019年6月我写了篇文章《深度学习的问题究竟在哪?》,说到深度学习的一个主要问...

jackli2020
50分钟前
24
0
什么是控制型人格,控制型人格的筛查测试

一、 什么是控制性人格 拥有控制型人格的人,他们会尽力的隐藏自己的意图,但是又会使用很微妙的方式来利用周围人的弱点,进而占取便宜时,使他们能够得到自己想要的东西。这类人的控制欲非常...

蛤蟆丸子
59分钟前
14
0
【Spring】Spring AOP 代理对象生成逻辑源码分析

1. spring aop案例(POJO注入) 1.0 被代理接口 TargetInterface /** * 被代理的接口 * @author Yang ZhiWei */public interface TargetInterface { void show(); String show......

ZeroneLove
今天
36
0
聊聊dubbo-go的gracefulShutdownFilter

序 本文主要研究一下dubbo-go的gracefulShutdownFilter gracefulShutdownFilter dubbo-go-v1.4.2/filter/filter_impl/graceful_shutdown_filter.go type gracefulShutdownFilter struct {......

go4it
今天
30
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部