wqy的B题

怼烎@ 2024-04-20 10:27 15阅读 0赞

##  ##

wqy的B题

### 题意： ###

> 和一道叫机器翻译的题差不多，不过这道题要难一些，没有规定必须删除最早入队的。

### 解法： ###

> 解法和\[POI2005\]SAM-Toy Cars这道题差不多，考虑贪心。  
> 每次选取下一次使用最远的点删除。  
> 拿个堆维护一下就好了。

### CODE: ###

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; #define LL long long #define N 200010 int n,k,a[N],nxt[N],last[N]; priority_queue<pair<int,int> > q,del; bool vis[N]; int main() { scanf("%d%d",&n,&k); for(int i = 1 ; i <= n ; i++) { scanf("%d",&a[i]); nxt[last[a[i]]] = i; last[a[i]] = i; } for(int i = 1 ; i <= N ; i++) { if(last[i]) nxt[last[i]] = n+1; } int ans = 0,size = 0; for(int i = 1 ; i <= n ; i++) { if(vis[a[i]]) { del.push(make_pair(i,a[i])); q.push(make_pair(nxt[i],a[i])); continue; } ans++; if(size < k) { vis[a[i]] = 1; size++; q.push(make_pair(nxt[i],a[i])); } else { while(!q.empty() && !del.empty() && q.top() == del.top()) q.pop(),del.pop(); int num = q.top().second; q.pop(); vis[num] = 0; vis[a[i]] = 1; q.push(make_pair(nxt[i],a[i])); } } printf("%d \n",ans); //system("pause"); return 0; }

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

发表评论取消回复

表情：

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

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

相关阅读

相关 wqy的C题

wqy的C题 > 毒瘤！题意： > 你有一张 $ n $ 个点 $ m $ 条边的无向图。 > 你想在这张图上添加 $ n $ 条有向边，每一条有向...

电玩女神/ 2024年04月20日 10:29/ 0 赞/ 20 阅读

相关 wqy的B题

wqy的B题题意： > 和一道叫机器翻译的题差不多，不过这道题要难一些，没有规定必须删除最早入队的。解法： > 解法和\[POI2005\]SA...

怼烎@/ 2024年04月20日 10:27/ 0 赞/ 16 阅读

相关 b与b不同(b和B的区别)

1、b和B的区别: b是bit的缩写，意思是比特位；B是Byte的缩写，意思是字节； byte为字节，bit为位，1byte=8bit。 1、bit 位：位是计算

素颜马尾好姑娘i/ 2023年09月23日 20:21/ 0 赞/ 136 阅读

相关 2013年-Java-B-真题

-------------------- 2013年-Java-B-题5 有理数类有理数就是可以表示为两个整数的比值的数字。一般情况下，我们用金丝的小数

桃扇骨/ 2022年12月22日 13:30/ 0 赞/ 90 阅读

相关 Codeforces Round #663 (Div. 2) B题

[题目链接][Link 1] include <cstdio> include <iostream> using namespace std

àì夳堔傛蜴生んèń/ 2022年11月26日 07:38/ 0 赞/ 181 阅读

相关 javascript 面试题 var a=b=0

(function () { var a = b = 0 })() console.log(b) 结果是 `b = 0`。分析：

短命女/ 2022年06月02日 11:26/ 0 赞/ 180 阅读

相关 CODEFORCE 246 Div.2 B题

题目例如以下： B. Football Kit time limit per test 1 second memory limit per test 256 mega

Love The Way You Lie/ 2022年03月31日 08:36/ 0 赞/ 194 阅读

相关 CodeForces - 1040B Shashlik Cooking（水题）

题目： B. Shashlik Cooking time limit per test 1 second memory limit per test 512 mega

た入场券/ 2022年01月06日 07:41/ 0 赞/ 549 阅读

相关 B. Sereja and Suffixes 水题

B. Sereja and Suffixes time limit per test 1 second memory limit per test 256 megaby

水深无声/ 2021年12月11日 08:01/ 0 赞/ 246 阅读

相关 codeforces 278Div1 B题

虚拟参赛的时候没想到是线段树，看到很多人都过了，也蛮着急的。首先用二分+线段树的方法更新DP\[i\]：它表示以A\[i\]为结尾可以最前到哪个位置；再用线段树计算an

痛定思痛。/ 2021年10月23日 07:23/ 0 赞/ 253 阅读