[POI2005]SAM-Toy Cars

左手的ㄟ右手 2024-04-20 10:28 69阅读 0赞

##  ##

\[POI2005\]SAM-Toy Cars

### 题意： ###

> 好像题意已经挺明白的了，[戳。][Link 1]

### 解法： ###

> 首先来想一下如何才能尽量少的取玩具. 显然,如果一个玩具已经在地上了,就可以不用去取. 但是地上能放的玩具的数量有限,所以我们可以记录每种玩具下一次要被玩的时间next\[i\],并在需要更换玩具的时候换走当前队列中next\[i\]最大的那一个玩具.  
> 所以我们可以得到这样一个贪心策略:要换玩具的时候,换next\[i\]最远的那个玩具。  
> 然后就是模拟一下入队出队情况,用优先队列维护一下next。

### CODE: ###

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; #define LL long long #define N 500010 #define M 100010 int n,k,p,a[N]; int nxt[N],ans; bool vis[M]; struct cmp { inline bool operator() (const int &a,const int &b) { return nxt[a] < nxt[b]; } }; queue <int> q1[M]; priority_queue <int,vector<int>,cmp> q2; int main() { scanf("%d%d%d",&n,&k,&p); for(int i = 1 ; i <= p ; i++) { scanf("%d",&a[i]); q1[a[i]].push(i); } for(int i = 1 ; i <= p ; i++) { q1[a[i]].pop(); if(q1[a[i]].empty()) nxt[i] = p + 1; else nxt[i] = q1[a[i]].front(); } for(int i = 1 ; i <= p ; i++) { if(!vis[a[i]]) { if(q2.size() == k) { vis[a[q2.top()]] = 0; q2.pop(); } q2.push(i); vis[a[i]] = 1; ans++; } else q2.push(i), k++; } printf("%d \n",ans); //system("pause"); return 0; }

转载于:https://www.cnblogs.com/Repulser/p/11409377.html

[Link 1]: https://www.luogu.org/problem/P3419

发表评论取消回复

表情：

评论列表（有 0 条评论，69人围观）

还没有评论，来说两句吧...

相关阅读

相关 [POI2005]SAM-Toy Cars

\[POI2005\]SAM-Toy Cars 题意： > 好像题意已经挺明白的了，[戳。][Link 1] 解法： > 首先来想一下如何才能尽量少...

左手的ㄟ右手/ 2024年04月20日 10:28/ 0 赞/ 70 阅读

相关 orbslam-car,rosbag

做：alias linux Linux alias命令用于设置指令的别名 alias 别名设置保存到文件：/root/.bashrc里面就可以了上述命令，使每次都

清疚/ 2023年01月21日 11:20/ 0 赞/ 106 阅读

相关 Car Pooling（C++拼车）

解题思路：（1）记录终点以及对应的乘客数 class Solution { public: bool carPooling(vector<

叁歲伎倆/ 2023年01月15日 12:29/ 0 赞/ 100 阅读

相关 SAP CAR 的主要优势

SAP CAR 的主要优势全渠道POS集成 SAP CAR通过引入新的多渠道数据模型，跨多渠道捕获销售交易。POS、销售订单和退货交易数据的一体化，能为客户提供360度全

短命女/ 2022年09月10日 13:18/ 0 赞/ 193 阅读

相关 SAP CAR简介

SAP CAR简介什么是SAP CAR？ SAP CAR是SAP Customer Activity Repository的缩写。SAP CAR由SAP HANA的实时计

短命女/ 2022年09月10日 13:16/ 0 赞/ 180 阅读

相关 VS（visual studio 2005）2005快捷键

VS（visual studio 2005）2005快捷键 Ctrl\+回车----上一行 Ctrl+E,D ----格式化全部代码 Ctrl+E,F ----格式

水深无声/ 2022年06月18日 10:13/ 0 赞/ 219 阅读

相关 1095. Cars on Campus (30)

Zhejiang University has 6 campuses and a lot of gates. From each gate we can collect the

╰+攻爆jí腚メ/ 2022年05月28日 00:45/ 0 赞/ 160 阅读

相关 CAR

CAR and DCAR在 Fast EtherChannel，Tunnel , Pri interface都不支持所有未启用ip cef的接口也都不支持。配置CAR前

迈不过友情╰/ 2022年01月13日 19:59/ 0 赞/ 199 阅读

相关 [POI2005]SKA-Piggy Banks tarjan 水题

Description Byteazar 有 N 个小猪存钱罐. 每个存钱罐只能用钥匙打开或者砸开. Byteazar 已经把每个存钱罐的钥匙放到了某些存钱罐里. Byt

忘是亡心i/ 2021年11月17日 16:26/ 0 赞/ 227 阅读

相关 Luogu3426 [POI2005]SZA-Template (KMP)（未完成）

未理解透，鬼知道怎么A的蒟蒻交了个乱猜贪心搞了10pts，一翻题解群佬乱舞，最后DP解决 $\\exists i - next\[i\] <= j, f\[j\] =

客官°小女子只卖身不卖艺/ 2021年11月17日 05:12/ 0 赞/ 159 阅读