文章

84

粉丝

408

获赞

31

访问

831.6k

头像
沙漠储油点(c++)
P1056
发布于2020年7月18日 11:29
阅读数 10.3k

参考:https://blog.csdn.net/daoqin121/article/details/39321481

首先明确一点:储油点的油都是卡车自己从起点一个个运过来的,即:卡车首先从起点跑若干趟将油运到第一个储油点,然后依次跑若干趟将油运往下一个储油点,最后距离终点500km时即可跑一趟就能到达终点

所以,从后往前分析,将距离终点最近的一个储油点设为第一个点,与终点的距离用数组dis存储,储油量用数组oil存储,dis[1] = 500, oil[1] = 500

由于卡车最大储油量为500L,所以(相较于起点而言的)前一个站点应该比后一个站点多500L油,这500L是用于两个站点之间的路程消耗

所以得出递推式:dis[i+1] = dis[i] + 500 / (2*i + 1), oil[i+1] = oil[i] + 500

最后输出的时候要记得将总路程减去dis之后逆向输出

#include<iostream>
using namespace std;
int main()
{
	int dis[100];
	int oil[100];
	dis[0] = oil[0] = 0;
	dis[1] = oil[1] = 500;
	
	int i, j;
	for (i = 1; dis[i] <= 1500; i++) {
		dis[i+1] = dis[i] + 500 / (2*i + 1);
		oil[i+1] = oil[i] + 500;
	}
	 
	while (1) {
		int sum;
		cin >> sum;
		if (sum == 0)
			break;
		for (j = i-1; j > 0 && dis[j] > sum; j--);
		for (int k = 1; j > 0; k++, j--) {
			cout << k << "  " << sum - dis[j] << "  " << oil[j] << endl;
		}
	}
	return 0;
}
...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发