Codeforces - 1334C 贪心
http://codeforces.com/contest/1334/problem/C
题意：
一共cas个查询，对于每个查询，顺时针排列n个怪物，每个怪物有两个属性，属性a表示生命值，属性b表示当前怪物死时自爆对下一个怪物产生的伤害，生命值<=0时视为死亡，你可以对怪物射击，每次射击伤害都是1，问最少开几枪，可以杀死所有怪物。
思路：
首先，每种怪物的死法，大体可以分成两种：
第一种就是这个怪物作为你射击的起点，也就是说它完全是被你打死的，对它的伤害没有来自它上一个怪物的自爆；
第二种就是对它的伤害有一部分来自它上一个怪物的自爆，如果它上一个自爆没能炸死它那还需要你补刀。
那我们只需要O(n)枚举起点就可以了，谁做起点谁自杀，然后顺时针这一圈除了起点位置，所有怪物都受到了上一个自爆产生的伤害。对于每个怪物来说，如果他的死法是第二种，那么这个伤害值是恒定的，即：
num[i] = max(0LL, p[i].a - p[id].b); //记num为怪物在第二种死法的条件下，我还需要打它几枪
然后我们记一下所有num的总和sum，sum就是这一圈怪物如果都是第二种死法，我一共需要打他们几枪。
接下来就枚举起点，因为起点是第一种死法，所以每次用sum减去起点如果是第二种死法产生的花费，
即：res -= num[i];
然后再加上起点被你打死需要的花费，也就是他的生命值，
即：res += p[i].a;
维护一个最小值即可。
AC代码：
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！