2021 ICPC 江西省大学生程序设计竞赛 J 二分 队列 模拟
2021/10/25 20:39:42
本文主要是介绍2021 ICPC 江西省大学生程序设计竞赛 J 二分 队列 模拟,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
你有一个可以调节容量的(存放数字)容器,一开始为空。
给你N次查询 。问有至少多大的容量能完成K次完美操作。
如果这个数字不在容器,并且容器满了,那就将最久之前查询的数从容器种删除,再加上这个数。如果容器没满就直接加入。
如果在容器就将这次查询称为完美操作。
题解思路
容器越大,完美操作数肯定越高。因为不会使别的数被删除。
所以容量具有单调性。
这样我们就可以二分枚举出这个答案了。log
这样我们需要在On内判断出枚举的答案的准确性。
我们利用哈希表和队列来模拟这个操作。
用哈希值来记录在不在容器里。
我们多次将这个值入队来保证权重,
而且在出队的时候一定要出队到真实值,即哈希值为1。
最多只会入队N次。
所以时间复杂度是可以的。
没开这题属实可惜。
AC代码
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <vector> #include <algorithm> #include <map> #include <string> #include <unordered_map> using namespace std; const int INF = 0x3f3f3f3f; int n , k ; int a[100100] ; bool che( int m ) { queue <int> q ; int re = 0 ,cnt = 0 ; unordered_map < int , int > mp ; for ( int i = 1 ; i <= n ; i++ ) { if ( mp[a[i]] != 0 ) { q.push(a[i]) ; mp[a[i]]++ ; re++ ; }else if ( cnt != m ) { q.push(a[i]) ; mp[a[i]] = 1 ; cnt++ ; }else { while ( cnt == m ) { int f = q.front(); q.pop(); mp[f]--; if ( mp[f] == 0 ) cnt--; } q.push(a[i]); mp[a[i]]++; cnt++; } } if ( re >= k ) return 1 ; else return 0 ; } int main () { ios::sync_with_stdio(false);cin.tie(0); cin >> n >> k ; for ( int i = 1 ; i <= n ; i++ ) { cin >> a[i] ; } int t1 = 1 , t2 = n ; while ( t1 < t2 ) { int mid = t1 + t2 >> 1 ; if ( che( mid ) ) { t2 = mid ; }else t1 = mid + 1 ; } if (che(t2)) cout << t2 << "\n" ; else cout << "cbddl\n" ; return 0 ; }
这篇关于2021 ICPC 江西省大学生程序设计竞赛 J 二分 队列 模拟的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板