你想吃癞蛤蟆肉吗

来源：蜘蛛抓取(WebSpider) 时间：2022-10-03 03:02 标签： 癞蛤蟆的吃法

"咦，你小子还算有些本事，这么难算的距离都被你算出来了" 原来是小A正确算出了自己与小C的距离

"这么遥远的距离，我该怎么去找她呢，她一定急坏了吧" 小A急切的说到

"有本大仙在，你这个担心不多余吗？你求我，我就带你去！" 小晋边说边翘起了二郎腿

"求你带我去见她" 小A心想着虽然男儿膝下有黄金，不应当随便求人，但是为了小C这点小事算什么！

"你以为求本大仙就有用了? 那我岂不是一点好处都没有，这样吧，你帮我赚点外快，我就带你过去，说话算话"

"好的，没问题，你快说吧" 小A嘴上这样说，心里却想着"##￥%#@#！￥...（略）"

你也知道，大陆是圆形的，在大陆的边缘有一条环形的道路，路上会有很多免费的天鹅肉领取处，假设第i个天鹅肉领取处可以领取gas[i]个天鹅肉

从第i个天鹅肉领取处到第i+1个天鹅肉领取处，我要吃掉cost[i]个天鹅肉，要是路途中没有足够的天鹅肉吃了，我就会动不了。所以我的要求就是：你帮我找到一个起点i，使我从第i个领取点出发，能绕大陆一圈后回到第i个领取点。

如果你不能让我吃遍整个大陆的天鹅肉，本大仙就不带你去见小C了。

注意,如果有很多点都可以当做起点，我想去编号最小的，本大仙就是这么任性！

"你一个蛤蟆，吃个鬼的天鹅肉！而且你最好说话算话，你个**" 当然这是小A的心里活动

有多组输入，请处理到EOF

接下来两行每行有n个整数，分别代表gas数组和cost数组。
数字范围不超过100且为正整数。在开始前小晋身上没有携带任何天鹅肉

输出一个数字，如果不存在能环绕一圈的方法则输出-1，否则输出最小的满足条件的起点，下标从0开始。 

0
4
【思路】：这题就是一个双指针，如果sum<0的话，就移动l，
如果大于的话就移动r，还有因为l的位置就是【0，n）；
所以我们就有了出口条件。
这题有个注意点，就是l动的时候，r不能动。
r动的时候，l不能动。
同时动的话会出事
附上一组有趣的数据（cwl学长给的）：
3
1 0 1
1 1 0
读者可能会怀疑这里会出现l>r的情况会导致wa。 其实并不会，最多就是l==r，不信的话你可以随便自己 因为【l，r】最坏就是l==r的情况 等于0就肯定跳出循环了。 所以不会出现l>r的情况。

我要回帖

更多关于 癞蛤蟆的吃法 的文章

 

随机推荐