[ABC268C] Chinese Restaurant
2023/5/19 1:22:05
本文主要是介绍[ABC268C] Chinese Restaurant,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
[ABC268C] Chinese Restaurant
声明:以下的所有操作都会再做一次 \(\% n+n) \% n\),比如 \(i - 1\) 会变成 \(((i-1)\%n+n)\%n\)
题意
有 \(n\) 个人和 \(n\) 个盘子,每个人如果能拿到 \(i - 1\) 或 \(i\) 或 \(i + 1\) 号盘子那么他会很开心,现在每个人的站位是 \(p_i\),他们的站位位置可以同时 $ + 1$,问最多可以有多少人觉得很开心。
思路
由于是一起动,所以可以用桶记录每个人走了多少步又到了那里,但是这样是 \(O(n^2)\) 的存不下也会超时。我们知道只有他在固定的盘子前才会觉得开心,所以有些桶是没用的,所以只要记录每个人到他想要去的盘子要多远就可以了,时间复杂度和空间复杂度为 \(O(n)\),在记录要走多远的时候,要注意细节。
代码
#include <iostream> using namespace std; const int MaxN = 2e5 + 10; int cnt[MaxN], p[MaxN], n, ans; int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> p[i]; cnt[n - ((p[i] - (i - 1 + n) % n) + n) % n]++, cnt[n - ((p[i] + n - i) + n) % n]++, cnt[n - ((p[i] + n - (i + 1) % n) + n) % n]++; } for (int i = 0; i < n; i++) { ans = max(ans, cnt[i]); } cout << ans << endl; return 0; }
这篇关于[ABC268C] Chinese Restaurant的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!