首页 > 代码库 > P1016 旅行家的预算
P1016 旅行家的预算
提高组贪心傻逼题。
不知道洛谷上的题解是怎么写的。
看BABA我的思路:
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define il inline using namespace std; il int gi() { int x=0,y=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) y=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=x*10+ch-‘0‘; ch=getchar(); } return x*y; } struct zhan { double dist,pri; }z[100045]; double mon[100045];//在每个加油站最便宜多少钱的油 int main() { double all,take,d,p,ans=0,lon; scanf("%lf%lf%lf%lf",&all,&take,&d,&p); lon=take*d;//每次该加油站最远可以到多远 int n; cin>>n; n++;//把起点加入加油站 z[1].dist=0; z[1].pri=p; for(int i=2;i<=n;i++) scanf("%lf%lf",&z[i].dist,&z[i].pri); n++; z[n].dist=all; for(int i=1;i<=n;i++) mon[i]=2e8;//赋初值 for(int i=1;i<n;i++) { for(int j=i+1;j<=n;j++) { if(lon+z[i].dist>=z[j].dist) { if(z[i].pri<mon[j])//从每个加油站往后看他能影响的加油站,如果更便宜就更新 mon[j]=z[i].pri; } else break; } } for(int i=2;i<=n;i++) if(mon[i]==2e8)//如果有一个加油站到不了 { printf("No Solution\n"); return 0; } for(int i=2;i<=n;i++) ans+=mon[i]*(z[i].dist-z[i-1].dist)/d;//你懂得 printf("%.2lf\n",ans); return 0; }
P1016 旅行家的预算
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。