P1016求调,50pts只过2,3测试数据
  • 板块学术版
  • 楼主songzhan
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/7/22 09:43
  • 上次更新2025/7/22 14:31:48
查看原帖
P1016求调,50pts只过2,3测试数据
695038
songzhan楼主2025/7/22 09:43
//献上我的屎山代码
//感谢各位大佬调我
//防止看不懂,作者加了注释awa 
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
double d1,c,d2,p;
int n;
double u,res;
struct node{
	double x,y;
}a[N];
struct nobe{
	double x1,y1,number;
}b[N];
bool cmp(nobe a,nobe b){
	return a.y1<b.y1;
}
bool cmp1(node a,node b){
	return a.x<b.x;
}
double ans,sum;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);//关闭输入输出流 
	cin>>d1>>c>>d2>>p>>n;
	a[0].x=0;a[0].y=p;//将起点距离与加油站价格加入总体进行计算 
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
		b[i].x1=a[i].x,b[i].y1=a[i].y;
		b[i].number=i;//将a数组所赋予的b数组数据编号 
	}
	bool flag=false;
	for(int i=0;i<n;i++){//如果有两个加油站距离大于车子可以行驶的距离,则无法到达目的地 
		if(a[i+1].x-a[i].x>c*d2){
			flag=true;
		}
	}
	if(d1-a[n].x>c*d2){//代码缺陷,单独判断最后一个加油站到目标城市距离是否大于汽车所能行驶距离 
		flag=true;
	}
	if(flag==true){//无法到达目的地输出 
		cout<<"No Solution";
		return 0;
	}
	sort(a+1,a+n+1,cmp1);//对数组进行与起始城市距离由大到小排序 
	sort(b+1,b+n+1,cmp);//这个数组排序是为了后面找汽车所能达到距离中加油站价格都大于自己所在加油站中最小价格的加油站 
	bool flag1=false;
	for(int i=0;i<=n;i++){
		bool flag1=false;
		double q=c*d2;//汽车满油所能行驶距离 
		double ii=n;
		for(int j=i+1;j<=n;j++){//判断汽车从当前加油站最多能到达哪个加油站 
			if(a[j].x-a[i].x<=q&&a[j+1].x-a[i].x>q)ii=j;
		}
		for(int j=i+1;j<=ii;j++){
			if(a[j].y<a[i].y){//判断后面加油站有没有比自己更便宜的 
				ans+=a[i].y*((a[j].x-a[i].x)/d2);//到达下个加油站需要多少油就加多少,坚决不搞剩余,把价格加在ans上 
				i=j;//满足条件,将汽车开到满足条件的加油站 
				flag1=true;//说明有满足条件的 
				break;
			}
		}
		if(i==n&&flag1==true){//在最后一个加油站且满足条件才开过来的时,直接到终点 
			ans+=((d1-a[i].x)/d2)*a[i].y;
			printf("%.2lf",ans);
			return 0;
		}
		if(flag1==false){//如果没有满足条件的 
			if(d1-a[i].x<=c*d2){//判断能不能直接开到终点 
				ans+=((d1-a[i].x)/d2)*a[i].y;
				printf("%.2lf",ans);
				return 0;
			}else{//如果不能 
				double o=0,o2=0;
				double q=c*d2;
				double ii=n;
				for(int j=i+1;j<=n;j++){
					if(a[j].x-a[i].x<=q&&a[j+1].x-a[i].x>q)ii=j;
				}
				u=(c-res)*d2;
				ans+=(c-res)*a[i].y;
				for(int j=i+1;j<=ii;j++){
					if(b[j].number>i){
						ans+=((b[j].x1-a[i].x)/d2-res)*a[i].y;
						res=u-(b[j].x1-a[i].x);
					}
				}
			}
		}
	}
	printf("%.2lf",ans);//输出答案 
	return 0;
}
2025/7/22 09:43
加载中...