POJ - 2698 贪心
2024-10-16 11:34:48
经典面替换算法,每次选择最远的那个碟片请求进行替换。
AC代码
#include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <utility> #include <string> #include <iostream> #include <map> #include <set> #include <vector> #include <queue> #include <stack> using namespace std; #pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10 #define inf 0x3f3f3f3f #define PI pair<int, int> typedef long long LL; const int maxn = 10000 + 5; queue<int>pos[maxn]; int a[105], driv[15]; int k, n; int solve() { int ans = 0, cnt = 0; for(int i = 0; i < n; ++i) { int ok = 0; for(int j = 0; j < cnt; ++j) { if(driv[j] == a[i]) { ok = 1; break; } } if(!ok) { ++ans; if(cnt < k) { driv[cnt++] = a[i]; } else if(cnt == k) { int ind = 0, far = -1; for(int j = 0; j < k; ++j) { int p = pos[driv[j]].empty() ? inf : pos[driv[j]].front(); if(p > far) { ind = j; far = p; } } driv[ind] = a[i]; } } pos[a[i]].pop(); } return ans; } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d%d", &k, &n); for(int i = 0; i < n; ++i) { scanf("%d", &a[i]); pos[a[i]].push(i); } printf("%d\n", solve()); } return 0; }
如有不当之处欢迎指出!
最新文章
- 自定义struts实现
- Robot Framework--01 创建简单工程示例
- Web 开发中 20 个很有用的 CSS 库
- 学习simple.data之基础篇
- Android日期时间格式国际化
- sessionStorage 、localStorage 和 cookie 之间的区别(转)
- winform 实现选择的城市名单
- 201521123056 《Java程序设计》第7周学习总结
- linux 巨页使用测试以及勘误1
- C# String StringBuilder 区别
- 喜怨交加C++
- jenkins pipline 发送邮件
- 小程序和H5互调
- PHP + JS 实现大文件分割上传
- 如何让一个Java新手快速入门?
- 从工程化角度讨论如何快速构建可靠React组件
- 在后台运行rtorrent
- 如何生成.p12文件
- linux后台启动程序脚本实例
- MySQL原生API、MySQLi面向过程、MySQLi面向对象、PDO操作MySQL