专栏文章

p1016旅行者的题解

P1016题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir0s96l
此快照首次捕获于
2025/12/04 13:53
3 个月前
此快照最后确认于
2025/12/04 13:53
3 个月前
查看原文

纪念蒟蒻的第一次切绿题没有看题解独自ac且一次过

其实也看了一下
题目链接[(https://www.luogu.com.cn/probleP1016)]
不难发现,只需要进行两种决策,一种是到达更便宜的油站,实在不行就奢侈一把,用98的好油,实际上都是跑那么点距离
从最简单的决策思考,一种跳出循环的方式即是找到更便宜的油站,撞狗屎运了,另一种便是去最远的地方去接点好油
q:那么如何跑到最远呢
a:很简单奢侈一把装满油即可 代码实现如下
CPP
#include<bits/stdc++.h>
using namespace std;
struct add{
	double qian;
	double di;
}a[10];
double ans=0;
double d,c,d2,p;
int n;
double now;//表当前油箱剩余的量
/*bool cmp(add x,add y){
	return x.qian<y.qian;
}抽象排序别看了
*/
int main(){
	cin>>d>>c>>d2>>p>>n;
	a[n+1].di=d;
	a[0].qian=p;
	for(int i=1;i<=n;i++){
		cin>>a[i].di>>a[i].qian;
		if(a[i].di-a[i-1].di>c*d2){//吃饱了跑不过去就躺地上说出那句话即可
			cout<<"No Solution"<<"\n";
			return 0;
		}
	}
	int j=0;
	for(int i=0;i<=n+1;i=j){
		for(j=i+1;j<=n+1;j++){//有且仅有两种跳出的方式
			if(a[j].di-a[i].di>c*d2){
				j--;
				break;
			}
            if(a[j].qian<a[i].qian){
				break;
			}
		}
		if(a[j].qian<a[i].qian){//有小的就跑去
			ans+=((a[j].di-a[i].di)/d2-now)*a[i].qian;
		}
		else {
			ans+=(c-now)*a[i].qian;
			now=c-(a[j].di-a[i].di)/d2;
		}//这里是实在没有小的了,能去的最远的距离,为什么这样写可以呢?
	}
	printf("%.2f\n",ans);//ans:因为每一步都是当前最优解
	return 0;
}
对了,感谢大佬@swkyccbb的思路,虽然您早已不在luogu但感谢您的思路
good bye

评论

0 条评论,欢迎与作者交流。

正在加载评论...