题目链接:http://acm.timus.ru/problem.aspx?space=1&num=1113
根据样例分析:
1、沙漠只有500公里或者更短,这时很简单,一次搞定。
2、沙漠600km,怎么办?我们需要保证的是:车到了离沙漠终点还有500km的地方,能恰恰加满油而且不
会有任何多余,方案其实很简单,从起点处加300升油,这300升油怎么用呢:开出100km,存下100
升,剩下100升刚好使得汽车返回起点。再在起点处加满500升油,这时就可以一路狂奔了,当然,要记得
开了100公里后,把存放在那儿的100升油也加上。(这时在起点的油一共是500+300)
3、我们先看看2的情况,符合这种情况的沙漠的最大距离是多少呢:答案是(500+500/3)公里。即在起
点准备1000升油,第一次装500升,跑了500/3公里后存放500/3升油,然后返回起点,这时车里的油也正
好用完,然后再在起点处装500升,跑了500/3公里后,把车内的(500-500/3)升油先放下,然后再一次
性把500升油装入车中。一路跑吧。
4。当沙漠的距离超过了(500+500/3)km(但又超过得不多)又当如何?这时我们可以把前面的(500+500/3)km看成一段整体,需要保证的是:在距离沙漠终点(500+500/3)km处恰恰有1000升油(由3的分析可知)。怎么来保证呢,我们假设沙漠的距离只比(500+500/3)多了1公里,因为汽车的容量是500升,所以1000升油最少从起点装3次油才能倒满(具体情况你可以自己想想)。除了3次装油,还有两次折回,所以往返正好有5次,这5次的能保证的距离是500/5,所以这时我们又把沙漠的距离延伸到了:(500+500/3+500/5),起点应该储备1500升油。
5。当沙漠的距离超过了(500+500/3+500/5)公里,我们要保证的是在距离沙漠终点(500+500/3+500/5)公里的
地方有1500升油。。。。。。。。
一路往下,总有某一个值使得dis =(500+500/3+500/5+..+500/(2k-1))<1000,但是
(500+500/3+500/5+..+500/2k-1+500/(2k+1))>1000,应该在起点准备多少油呢?这时多了一小段出来
,很像情形2的分析了,说白了,在起点准备的油应当是:(1000 -dis)*往返次数 + k*500。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define inf 1<<30
#define mod 1000000007
using namespace std;
int main()
{
int k;
double n,m;
scanf("%lf%lf",&n,&m);
double sum=;
for(k=;sum+m/(*k-)<n;k++)sum+=m/(*k-);
double ans=(k-)*m+(*k-)*(n-sum);
printf("%.0f",ceil(ans));
}