【Atcoder yahoo-procon2019-qual D】 Ears
2024-10-19 14:35:10
Atcoder yahoo-procon2019-qual D
题意：给你\(L\)个耳朵（？？？），以及一条范围从\(0\)到\(L\)的数轴，你可以选择一个出发点，从该点开始随意走动，如果经过了\(i-0.5\)这个点，则会给第\(i\)个耳朵的数值\(+1\)，每个耳朵都有一个最终的要求值，你可以通过增加或减少一个耳朵的数值来达到要求值，问最少更改的次数。
思路：
走的路线是这样的（或者左右颠倒）：
首先往左一段距离；
再向右一段距离（超过原点）；
再向左一段距离（不超过原点）。
然后就可以预处理出三段分别的最小值：
- 最左点到原点（可给耳朵赋的值是非\(0\)偶数）
- 原点到结束点（可给耳朵赋的值是奇数）
- 结束点到最右点（可给耳朵赋的值是非\(0\)偶数）
然后就可以稍微递推一下了。
反思：比赛时的思路第一开始都没考虑到最后还可能折返一段距离，于是就挂了第一次，第二次是\(i+1\)写成\(i\)了（可以这么说，但是我以为的错误是还要加上一段不超过最右点的向右折返，然后加上了个没用的东西）。所以第一开始最好还是考虑更完善一些。
最新文章
- 关于Openlayer3的菜鸟认识
- Spring实现IOC
- 【CodeForces 261B】Maxim and Restaurant（DP，期望）
- Inno Setup制作应用程序安装包
- Hadoop中客户端和服务器端的方法调用过程
- Excel报表开发
- Array.prototype.each
- python 数据类型（sequence 序列、dictionary 词典、动态类型）
- CSS理解之padding--非原创
- 关于VS 2010 RDLC 报表的详细使用说明
- iOS-桥接方式
- Linux学习第三步(Centos7安装mysql5.7数据库)
- java native用法
- SpringBoot------连接MySQL报错:The server time zone value 'Öйú±ê׼ʱ¼ä' is unrecognized
- TransmittableThreadLocal 解决 线程池线程复用 无法复制 InheritableThreadLocal 的问题.
- .NET Core HttpClient调用腾讯云对象存储Web API的"ERROR_CGI_PARAM_NO_SUCH_OP"问题
- 06: linux中find查找命令总结
- Python -- Gui编程 -- Qt库的使用 -- 布局与基本控件
- reason: image not found的解决方案
- P,NP,NPC的通俗解释