欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces 1010A - Fly

程序员文章站 2024-03-17 15:12:58
...

链接:Codeforces 1010A - Fly

大意:从地球飞到火星要经过n-2个星球,最后返回地球则是直接返回,每个星球起飞和降落都需要燃料,且效率不同。已知火箭自重为m,星球数n(包括地球和火星),以及每个星球起飞降落时的燃料效率ai和bi,求出发时需携带的最小燃料量,若不可行,输出-1。(2<=n<=1000,1<=m,ai,bi<=1000)

思路:最优解显然是最后降落时剩余燃料为0,所以反向模拟即可。考虑从地球直接飞往火星最后飞回地球,每个星球起飞或者降落时有等式:消耗燃料重量*效率=(火箭自重+剩余燃料重量+消耗燃料重量),由此可得:消耗燃料重量=(火箭自重+剩余燃料重量)/(效率-1)。显然当效率<=1时,火箭无法降落或起飞,此时应输出-1。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

double takeoff[1001];
double landing[1001];

int main()
{
	int n;
	double m;
	while (cin >> n)
	{
		bool impossible = false;
		double res = 0.0, tmp = 0.0;
		cin >> m;
		memset(takeoff, 0, sizeof(takeoff));
		memset(landing, 0, sizeof(landing));
		for (int i = 0; i < n; i++)
		{
			cin >> takeoff[i];
			if (takeoff[i] <= 1)
				impossible = true;
		}
		for (int i = 0; i < n; i++)
		{
			cin >> landing[i];
			if (landing[i] <= 1)
				impossible = true;
		}
		if (impossible)
			cout << -1 << endl;
		else
		{
			tmp = m / (landing[0] - 1);
			m += tmp;
			res += tmp;
			for (int i = n - 1; i >= 0; i--)
			{
				tmp = m / (takeoff[i] - 1);
				m += tmp;
				res += tmp;
				if (i != 0)
				{
					tmp = m / (landing[i] - 1);
					m += tmp;
					res += tmp;
				}
			}
			printf("%.10f\n", res);
		}
	}
	return 0;
}