cf896 B. Ithea Plays With Chtholly
2022/4/5 6:20:28
本文主要是介绍cf896 B. Ithea Plays With Chtholly,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意:
交互题。有n个位置,m次输入,和一个上限c。每次读入一个数x,输出把x放到哪个位置(可以覆盖)。目标是n个位置上都有数且单调不减。
\(1\le x\le c, 1\le c\le 1000,1\le n\cdot \lceil \frac c2 \rceil \le m \le 1000\)
思路:
先考虑一种朴素放法:对于每个x,从左到右找第一个空的或者比x大的位置放上去。那么每个位置最多放c次,n个位置不超过nc次。
考虑另一种放法:若x小于c/2,从左到右找第一个空的或者比x大的位置放上去;否则,从右到左找第一个空的或者比x小的位置放上去。这样任何时候数列都形如 “数数数空空数数数数”,每个位置最多放c/2次,能满足题目的范围。
const signed N = 1003; int n, m, c, cnt, a[N]; signed main() { cin >> n >> m >> c; while(cnt < n) { int x; cin >> x; if(x <= c/2) { int p = 1; while(a[p] && a[p] <= x) p++; if(!a[p]) cnt++; a[p] = x; cout << p << endl; } else { int p = n; while(a[p] && a[p] >= x) p--; if(!a[p]) cnt++; a[p] = x; cout << p << endl; } } }
这篇关于cf896 B. Ithea Plays With Chtholly的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding