Delicious Apples

Problem's Link: http://acm.hdu.edu.cn/showproblem.php?pid=5303

---

Mean:

一条长为L的环形路上种着n棵苹果数。

第i棵苹果数的位置在xi，有ai个苹果，苹果树的位置按顺时针顺序给出，且都是整数。

在0位置有一个仓库，有一个容量为k的篮子，需要使用这个篮子将所有苹果收到仓库中来，求全过程的最短路。

analyse:

首先来分析：

跑整圈的情况只可能出现一次。因为根据贪心的思想，摘完一个单边上最后那颗苹果树后发现背包还有剩余空间，此时才需要判断是否需要绕过中点到另一个单边去摘那个单边上的最后一棵苹果树上的苹果。其他情况都是直接摘满就回仓库就行。

由于苹果的数量不是很多，首先对每个苹果的位置进行离散。

把圆环从中点劈开，得到两个半圆。对于每个半圆，我们先尽可能多的拿掉k的整数倍个苹果。

剩下的都是离中点最近的苹果，而且这些苹果的数量一定小于2*k，也就是说剩下的这些苹果我们可以最多两次将它拿完。

怎么拿呢？

无非这三种方法：

最后我们枚举一下这三种情况，然后取最小路程加入到answer中即可。

Time complexity: O(N)

Source code: 

最新文章

1. 【数据采集】VBA数据采集可用 COM 组件
2. 【学】React的学习之旅3 - 添加事件(onClick)
3. 学习的目的：理解<转>
4. 给编译好的DLL增加签名
5. xml的语法与创建
6. 老的acm & oj学习站点
7. Android 自定义View高级特效，神奇的贝塞尔曲线
8. what does Html.HiddenFor () for ?
9. javascript实现页面右侧在线客服始终跟随鼠标滚动而上下滚动且始终位于屏幕中间
10. [刷题]算法竞赛入门经典(第2版) 5-15/UVa12333 - Revenge of Fibonacci
11. PHP学习之旅——PHP环境搭建
12. machine learning 之 导论 一元线性回归
13. 【原】无脑操作：Centos 7后台运行及终止jar包程序
14. Java HashMap 使用了未经检查或不安全的操作
15. javascript基础之函数
16. linux常用命令简介
17. C#-MVC开发微信应用(5)--自动应答系统-自动回复机器人
18. HZAU2018年十大阅读之星演讲稿
19. MongoDB高可用架构：Replica Sets+Sharding
20. Openstack入门篇（十八）之Cinder服务-->使用NFS作为后端存储

热门文章

1. [Aaronyang] 写给自己的WPF4.5 笔记24 [与winform交互-flash-DEMO-收尾篇1/6]
2. 每日英语：Mistrust Between U.S., Malaysia Strains Probe
3. TextView使用SpannableString设置复合文本(转)
4. 【Python】winpython下的包安装
5. 【css】ie6 和 ie7 下 position 与 overflow 的问题
6. 云服务器 ECS Linux 系统盘数据转移方法
7. Java WebService 简单实例[转]
8. 点击弹出 +1放大效果 -- jQuery插件
9. Spark源码系列（二）RDD详解
10. 使用before、after伪类制作三角形