[POI2005]Toy Cars

时间:2022-09-02 13:12:54

题目大意:
  有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的更多相关文章

  1. 洛谷 P3419 &lbrack;POI2005&rsqb;SAM-Toy Cars

    P3419 [POI2005]SAM-Toy Cars 题目描述 Johnny is a little boy - he is only three years old and enjoys play ...

  2. &lbrack;POI2005&rsqb;SAM-Toy Cars 贪心&plus;堆

    [POI2005]SAM-Toy Cars 题目:Jasio 是一个三岁的小男孩,他最喜欢玩玩具了,他有n 个不同的玩具,它们都被放在了很高的架子上所以Jasio 拿不到它们:为了让他的房间有足够的空 ...

  3. 周赛-Toy Cars 分类: 比赛 2015-08-08 15&colon;41 5人阅读 评论&lpar;0&rpar; 收藏

    Toy Cars time limit per test 1 second memory limit per test 256 megabytes input standard input outpu ...

  4. BZOJ1528&colon; &lbrack;POI2005&rsqb;sam-Toy Cars

    1528: [POI2005]sam-Toy Cars Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 282  Solved: 129[Submit][S ...

  5. &lbrack;POI2005&rsqb;SAM-Toy Cars

    题目描述 Johnny is a little boy - he is only three years old and enjoys playing with toy cars very much. ...

  6. bzoj 1528 &lbrack;POI2005&rsqb;sam-Toy Cars 堆维护&plus;贪心

    1528: [POI2005]sam-Toy Cars Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 716  Solved: 306[Submit][S ...

  7. Codeforces Round &num;303 &lpar;Div&period; 2&rpar; A&period; Toy Cars 水题

     A. Toy Cars Time Limit: 20 Sec  Memory Limit: 256 MB 题目连接 http://codeforces.com/contest/545/problem ...

  8. 【BZOJ 1528】 1528&colon; &lbrack;POI2005&rsqb;sam-Toy Cars (贪心&plus;堆)

    1528: [POI2005]sam-Toy Cars Description Jasio 是一个三岁的小男孩,他最喜欢玩玩具了,他有n 个不同的玩具,它们都被放在了很高的架子上所以Jasio 拿不到 ...

  9. 【BZOJ1528】&lbrack;POI2005&rsqb;sam-Toy Cars 贪心

    [BZOJ1528][POI2005]sam-Toy Cars Description Jasio 是一个三岁的小男孩,他最喜欢玩玩具了,他有n 个不同的玩具,它们都被放在了很高的架子上所以Jasio ...

随机推荐

  1. 如何使用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 - ...

  2. 适配iOS10以及Xcode8

    现在在苹果的官网上,我们已经可以下载到Xcode8的GM版本了,加上9.14日凌晨,苹果就要正式推出iOS10系统的推送了,在此之际,iOS10的适配已经迫在眉睫啦,不知道Xcode8 beat版本, ...

  3. css position static &vert; absolute &vert; fixed &vert; relative

    <div id="bigbox1">    <div id="box1" class="box">box1</ ...

  4. ubuntu卸载java

    Try this command: java -version If 1.6* comes then try: sudo apt-get autoremove openjdk-6-jre If 1.7 ...

  5. &ast;ecshop 首页促销价显示倒计时

    1.打开includes/lib_goods.php 找到 get_promote_goods()函数部 在(注意:位置别找错了,大概在394行位置) $goods[$idx]['url'] = bu ...

  6. 让页脚footer永远固定在页面的底部,而不是永远固定在显示器屏幕的底部的方法

    <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8&quo ...

  7. 如何解决Ora-04031错误(转)

    诊断并解决ORA-04031 错误 当我们在共享池中试图分配大片的连续内存失败的时候,Oracle首先清除池中当前没使用的所有对象,使空闲内存块合并.如果仍然没有足够大单个的大块内存满足请求,就会产生 ...

  8. 从零开始学习前端JAVASCRIPT — 6、JavaScript基础DOM

    1:DOM(Document  Object  Model)的概念和作用 document对象是DOM核心对象:对html中的内容,属性,样式进行操作. 节点树中节点之间的关系:父子,兄弟. 2:DO ...

  9. io类型

    非阻塞io from socket import * import time s=socket(AF_INET,SOCK_STREAM) s.bind(('127.0.0.1',8080)) s.li ...

  10. 记踩坑--Flask Web开发:S6电子邮件 ----&lbrack;Errno 11004&rsqb; getaddrinfo failed

    必须要记录下踩过的坑,一来,为后来者铺路,二来,实在摔得疼,提醒自己写代码要谨小慎微. [Errno 11004] getaddrinfo failed 1.先排除邮箱账号和授权码的错误 测试如下代码 ...