题目名称	1160. [NOIP 1999]旅行家的预算
输入输出	`lyuxing.in/out`
难度等级	★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	4
题目来源	王者自由于2012-10-16加入
开放分组	全部用户
提交状态
分类标签	分治贪心数学
	分享题解

通过：122，提交：337，通过率：36.2%
nsnsjsjjs	100	0.000 s	0.00 MiB	C++
LGLJ	100	0.000 s	0.00 MiB	C++
syzhaoss	100	0.000 s	0.00 MiB	C++
wow草原	100	0.000 s	0.00 MiB	C++
李奇文	100	0.000 s	0.00 MiB	C++
筽邝	100	0.000 s	0.19 MiB	Pascal
lqwang1985	100	0.001 s	0.17 MiB	Pascal
王者自由	100	0.001 s	0.17 MiB	Pascal
lyl610	100	0.001 s	0.17 MiB	Pascal
王者自由	100	0.001 s	0.18 MiB	Pascal

关于旅行家的预算的近10条评论(全部评论)
No Solution 复制粘贴时少复制个n。。。。。 HeHe 2017-07-05 10:33 7楼
#include<cstdio> #include<cmath> #include<algorithm> #define precision 0.0001 #define maxn 1000 using namespace std; struct tnode{double d,p;}a[maxn+10]; double d1,c,d2,p; int n; bool cmp(tnode xx,tnode yy) { return xx.d<yy.d; } int main() { // freopen("lyuxing.in","r",stdin); // freopen("lyuxing.out","w",stdout); int i,j,k; double s,ans,x,y; scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&p,&n); a[1].d=0,a[1].p=p; a[2].d=d1,a[2].p=0; for(n+=2,i=3;i<=n;i++)scanf("%lf%lf",&a[i].d,&a[i].p); sort(a+1,a+n+1,cmp); k=1,ans=x=0,s=cd2; while(k<=n) { if(a[k+1].d-a[k].d>s){printf("No Solution\n");return 0;} for(j=k+1;a[j].d-a[k].d<=s && j<=n;j++) if(a[j].p<=a[k].p) { y=(a[j].d-a[k].d)/d2; if(x<y)ans+=a[k].p(y-x),x=0; else x-=y; k=j; break; } if(fabs(a[k].d-d1)<=precision) { printf("%.2lf\n",ans); return 0; } if(j!=k) { ans+=a[k].p*(c-x); x=c-(a[k+1].d-a[k].d)/d2; k++; } } return 0; } jjky 2016-10-23 22:03 6楼
我竟然把文件名读成刘醒。。。 Janis 2016-08-07 11:53 5楼
对于每一次到达站点的时候都进行决策: 寻找距离当前站最近的比当前站便宜的站点　　如果找到了，油量够就直接开过去，油量不够就冲到刚好可以开过去如果找不到，就到前面找一个充满油量能到得了的最便宜的站点，充满油开过去。如果加满油找不到任何站点，那就输出No Solution Sky_miner 2016-05-06 06:15 4楼
数据没问题啊 cstdio 2012-11-03 11:32 3楼
那你怎么过第一个数据...... 风起时 2012-10-22 20:53 2楼
第一个数据错了 Rotide 2012-10-19 20:21 1楼

1160. [NOIP 1999]旅行家的预算

★☆ 输入文件：lyuxing.in 输出文件：lyuxing.out 简单对比
时间限制：1 s 内存限制：128 MiB

【问题描述】

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。

给定两个城市之间的距离$D1$、汽车油箱的容量$C$(以升为单位)、每升汽油能行驶的距离$D2$、出发点每升汽油价格$P$和沿途油站数$N(0\leq N\leq 10)$，油站$i$离出发点的距离$Di$、每升汽油价格$Pi(1\leq i\leq N)$。

【输入格式】

第一行，五个数字$D1，C，D2，P，N$。

接下来$N$行，每行两个为油站$i$离出发点的距离$Di$和每升汽油价格$Pi$。

【输出格式】

一行一个数字，表示最小费用，计算结果四舍五入至小数点后两位。

如果无法到达目的地，则输出No Solution。

【输入样例】

275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2

【输出样例】

26.95