http://codeforces.com/contest/864/problem/C
题意:
坐标轴上有x = 0和 x = a两点,汽车从0到a之后掉头返回,从a到0之后又掉头驶向a。。。从0到a或者从a到0叫做一次旅行。汽车的油箱的容量为b,行驶1单位长度消耗的油量为1单位,在x = f处有一个加油站,可以把油加满。
现在,汽车位于x = 0处,将要进行k次旅行,开始汽车的油箱是满的,问至少要加多少次油才能走完全程,或者不可能时输出“-1”。
思路:
可以把汽车的旅行看成是一直向前的,那么旅途中就有k个加油站,我们首先保证能够走到第一个加油站,之后根据贪心原则,走不到下一个加油站就在当前加油站加油,加了油之后都走不到的话,那就永远没有办法走到了。。。
最后再判断一下是否可以走完最后一个加油站到终点的路程即可。
代码:
#include <stdio.h> int main()
{
long long a,b,f,k; scanf("%lld%lld%lld%lld",&a,&b,&f,&k); long long now = b; long long ans = ; if (now < f) printf("-1\n");
else
{
now -= f;
for (int i = ;i < k;i++)
{
long long d = (i & ) ? (a - f) : f; d <<= ; if (d > now) ans++,now = b;
if (d > now)
{
printf("-1\n");
return ;
} now -= d;
} long long d = (k & ) ? a - f : f; if (d > now) ans++,now = b;
if (d > now) printf("-1\n");
else printf("%d\n",ans);
} return ;
}