题目大意:
有n种物品,地上有k个格子,p次操作。
每次操作要求将某一个指定的物品移动到任意一个格子中,同时你可以选择是否将格子中的某一个物品收起来,并消耗1的代价。
如果下达指令时,这个物品刚好在格子上,那么就不会消耗代价。
问至少消耗多少代价?
思路:
贪心。
每次移动如果时,如果地板上已经放慢了物品,那么就应该把第二次出现最晚的物品收起来。
预处理每一次指令对应的物品第二次出现的时刻。
用一个堆来维护当前地板上的物品即可。
#include<cstdio>
#include<cctype>
#include<hash_set>
#include<ext/pb_ds/priority_queue.hpp>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const int N=,P=;
int a[P],cnt[N],pos[N],next[P];
__gnu_cxx::hash_set<int> set;
__gnu_pbds::priority_queue<std::pair<int,int> > q;
__gnu_pbds::priority_queue<std::pair<int,int> >::point_iterator p[N];
int main() {
const unsigned n=getint(),k=getint(),p=getint();
for(register unsigned i=;i<=p;i++) {
a[i]=getint();
cnt[a[i]]++;
}
for(register unsigned i=;i<=n;i++) pos[i]=p+;
for(register unsigned i=p;i;i--) {
next[i]=pos[a[i]];
pos[a[i]]=i;
}
unsigned ans=,i=;
for(;set.size()<k&&set.size()<n&&i<=p;i++) {
if(!set.count(a[i])) {
ans++;
set.insert(a[i]);
::p[a[i]]=q.push(std::make_pair(next[i],a[i]));
} else {
q.modify(::p[a[i]],std::make_pair(next[i],a[i]));
}
}
for(;i<=p;i++) {
if(!set.count(a[i])) {
ans++;
set.erase(q.top().second);
q.pop();
set.insert(a[i]);
::p[a[i]]=q.push(std::make_pair(next[i],a[i]));
} else {
q.modify(::p[a[i]],std::make_pair(next[i],a[i]));
}
}
printf("%u\n",ans);
return ;
}
[POI2005]Toy Cars的更多相关文章
-
洛谷 P3419 [POI2005]SAM-Toy Cars
P3419 [POI2005]SAM-Toy Cars 题目描述 Johnny is a little boy - he is only three years old and enjoys play ...
-
[POI2005]SAM-Toy Cars 贪心+堆
[POI2005]SAM-Toy Cars 题目:Jasio 是一个三岁的小男孩,他最喜欢玩玩具了,他有n 个不同的玩具,它们都被放在了很高的架子上所以Jasio 拿不到它们:为了让他的房间有足够的空 ...
-
周赛-Toy Cars 分类: 比赛 2015-08-08 15:41 5人阅读 评论(0) 收藏
Toy Cars time limit per test 1 second memory limit per test 256 megabytes input standard input outpu ...
-
BZOJ1528: [POI2005]sam-Toy Cars
1528: [POI2005]sam-Toy Cars Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 282 Solved: 129[Submit][S ...
-
[POI2005]SAM-Toy Cars
题目描述 Johnny is a little boy - he is only three years old and enjoys playing with toy cars very much. ...
-
bzoj 1528 [POI2005]sam-Toy Cars 堆维护+贪心
1528: [POI2005]sam-Toy Cars Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 716 Solved: 306[Submit][S ...
-
Codeforces Round #303 (Div. 2) A. Toy Cars 水题
A. Toy Cars Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/contest/545/problem ...
-
【BZOJ 1528】 1528: [POI2005]sam-Toy Cars (贪心+堆)
1528: [POI2005]sam-Toy Cars Description Jasio 是一个三岁的小男孩,他最喜欢玩玩具了,他有n 个不同的玩具,它们都被放在了很高的架子上所以Jasio 拿不到 ...
-
【BZOJ1528】[POI2005]sam-Toy Cars 贪心
[BZOJ1528][POI2005]sam-Toy Cars Description Jasio 是一个三岁的小男孩,他最喜欢玩玩具了,他有n 个不同的玩具,它们都被放在了很高的架子上所以Jasio ...
随机推荐
-
如何使用yum 下载 一个 package ?如何使用 yum install package 但是保留 rpm 格式的 package ? 或者又 如何通过yum 中已经安装的package 导出它,即yum导出rpm?
注意 RHEL5 和 RHEL6 的不同 How to use yum to download a package without installing it Solution Verified - ...
-
适配iOS10以及Xcode8
现在在苹果的官网上,我们已经可以下载到Xcode8的GM版本了,加上9.14日凌晨,苹果就要正式推出iOS10系统的推送了,在此之际,iOS10的适配已经迫在眉睫啦,不知道Xcode8 beat版本, ...
-
css position static | absolute | fixed | relative
<div id="bigbox1"> <div id="box1" class="box">box1</ ...
-
ubuntu卸载java
Try this command: java -version If 1.6* comes then try: sudo apt-get autoremove openjdk-6-jre If 1.7 ...
-
*ecshop 首页促销价显示倒计时
1.打开includes/lib_goods.php 找到 get_promote_goods()函数部 在(注意:位置别找错了,大概在394行位置) $goods[$idx]['url'] = bu ...
-
让页脚footer永远固定在页面的底部,而不是永远固定在显示器屏幕的底部的方法
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8&quo ...
-
如何解决Ora-04031错误(转)
诊断并解决ORA-04031 错误 当我们在共享池中试图分配大片的连续内存失败的时候,Oracle首先清除池中当前没使用的所有对象,使空闲内存块合并.如果仍然没有足够大单个的大块内存满足请求,就会产生 ...
-
从零开始学习前端JAVASCRIPT — 6、JavaScript基础DOM
1:DOM(Document Object Model)的概念和作用 document对象是DOM核心对象:对html中的内容,属性,样式进行操作. 节点树中节点之间的关系:父子,兄弟. 2:DO ...
-
io类型
非阻塞io from socket import * import time s=socket(AF_INET,SOCK_STREAM) s.bind(('127.0.0.1',8080)) s.li ...
-
记踩坑--Flask Web开发:S6电子邮件 ----[Errno 11004] getaddrinfo failed
必须要记录下踩过的坑,一来,为后来者铺路,二来,实在摔得疼,提醒自己写代码要谨小慎微. [Errno 11004] getaddrinfo failed 1.先排除邮箱账号和授权码的错误 测试如下代码 ...