当前位置:首页 > 题解目录 > 正文内容

公路(road)

亿万年的星光4个月前 (10-01)题解目录498

【题目描述】

小苞准备开着车沿着公路自驾。

公路上一共有n个站点,编号为从1 到n。其中站点i与站点i+1 的距离为vi公里。

公路上每个站点都可以加油,编号为i 的站点一升油的价格为ai元,且每个站点只出售整数升的油。

小苞想从站点1 开车到站点n,一开始小苞在站点n且车的油箱是空的。已知车的油箱足够大,可以装下任意多的油,且每升油可以让车前进d公里。问小苞从站点1开到站点n,至少要花多少钱加油?

【输入描述】

       输入的第一行包含两个正整数n和d,分别表示公路上站点的数量和车每升油可以前进的距离。

输入的第二行包含n-1个正整数v1,v2,v3...Vn-1分别表示站点间的距离。

输入的第三行包含n个正整数a1,a2,a3...an分别表示在不同站点加油的价格。

【输出描述】

       输出一行,仅包含一个正整数,表示从站点1开到站点n,小苞至少要花多少钱加油。

【样例输入】

5 4
10 10 10 10
9 8 9 6 5

【样例输出】

79

【提示】

【样例 1 解释】

最优方案下:小苞在站点1买了3升油,在站点2购买了 5升油,在站点 4购买了2升油。

【数据范围】

对于所有测试数据保证1n105 ,1d≤10^5 ,1vi10^5 ,1ai10^5 。

【题目分析】

过程图解参考如下:

(1)首先,1号油站必须买油,否则动不了。

(2)考虑贪心策略,一开始所有的数据都是已知的,如果我们到到达n点发现没有油了,应该从n点(假设是3点)以前的加油站中挑选一个价格最低且能到达下一个加油站

(3)数据量比较大,要开long long。

(4)注意油箱足够大,可以装无限多的油。

(5)没有必要在最后一个站点n加油,因为我们的目的就是到n。


【参考答案】

#include <bits/stdc++.h>
using namespace std;
int v[100005], price[100005]; //距离和价格 
int n, d; //n个站点,d表示每升油可以前进的距离 
long long ans = 0, s = 0; //ans表示总费用,s表示 站点和站点之间的距离和 
int main() {
    scanf("%d%d", &n, &d);
    for (int i = 1; i < n; i++){
    	scanf("%d", &v[i]);   //n-1个站点之间的距离 
	} 
    int minn = INT_MAX; //最小值 
    for (int i = 1; i < n; i++) {
        scanf("%d", &price[i]); //读入价格 
        s += v[i]; //累计站点和站点之间的距离和 
        minn = min(minn, price[i]);  //找到到当前站点的最低油价 
        //距离小于0说明上次加的油可以走的更远,就是还有油 
		if (s > 0) {
        	// 总价钱=距离*油价
			int distance =  (s + d - 1) / d ; //到目前为止的距离(走了一站) 
            ans += distance* minn;  //累计价钱 
            s -= distance* d; // 往前走, 
        }
    }
    printf("%lld\n", ans);
    return 0;
}



【参考答案2】

#include <bits/stdc++.h>
using namespace std;
long long n,d,sum,a[100010],v[100010],mi[100010];
signed main() {
	cin>>n>>d;
	for(int i=1; i<n; i++) {
		cin>>v[i];
		v[i]=v[i-1]+v[i];//把距离做叠加起来,距离和 
	}
	for(int i=1; i<=n; i++)
		cin>>a[i]; //价格 
	mi[1]=a[1]; //第一个点必须加油 
	for(int i=2; i<=n; i++) 
		mi[i]=min(mi[i-1],a[i]); //维护前缀最小值
	int now=0;//now保存的是当前距离起点多少距离
	for(int i=1; i<n; i++) {
		if(now>v[i]) 
			continue;//如果超过了i+1的距离,那么就不用考虑当前加油站买油,直接考虑下一个加油站
		int k=ceil((v[i]-now)*1.0/d*1.0);//买的最少升数
		sum+=k*mi[i];//钱
		now+=k*d;//距离
	}
	cout<<sum;
	return 0;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

标签: CSPJ
分享给朋友:
返回列表

上一篇:小苹果(apple)

下一篇:植树节

相关文章

【题解】山区建小学

【题目描述】政府在某山区修建了一条道路,恰好穿越总共m个村庄的每个村庄一次,没有回路或交叉,任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di(为正整数),其中,0<i<...

字符串移位包含问题

【题目描述】对于一个字符串来说,定义一次循环移位操作为:将字符串的第一个字符移动到末尾形成新的字符串。给定两个字符串 s_1s1 和 s_2s2,要求判定其中一个字符串是...

【题解】均分蛋糕

【题解】均分蛋糕

【题目描述】小明的生日要到了!根据习俗,他需要将一些派分给大家。他有 N 个不同口味、不同大小的派。有 F 个朋友会来参加我的派对,每个人会拿到一块派(必须一个...

【题解】游戏

【题目描述】上了半天的物理数学课,大家的脑子有点转不动了,下午的课表似乎看透了同学们的 心思,第一节就安排了体育课,CZ 中学的课表真是太有爱了,赞一个!午间休息后,文体 委员小 S 喊大家到教室外的...

质数环

【题目描述】有一个整数n,把从1到n的数字无重复的排列成环,且使每相邻两个数(包括首尾)的和都为素数,称为素数环。为了简便起见,我们规定每个素数环都从1开始。例如,下面就是6的一个素数环。1 4 3...

【题解】取余(2019青岛市程序设计竞赛)

【问题描述】给你n个正整数a1,a2,..,an。求(a1*a2*..an)%10007的值。【输入】第一行,n,表示整数的个数。第二行,n个用空格隔开的正整数。【输出】一个整数,(a1*a2*..a...