P1016 旅行家的预算

贪心求,在当前点如果能到达距离最近的油价比他小的就直接去油价比他小的,

如果在可行范围内没有比他油价小的,就加满开到可行范围内油价最小的点;

这么做是对的,我不会证明;

还有就是,如果变量定义在外面了,在for循环里面就不要定义了,这个点卡了我一下午;

一直停止运行……

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
typedef double dd; struct node
{
dd p,dis;
}s[maxn]; dd all_dis,capa,per_dis,st_p;
int n; bool cmp(node qw,node we)
{
return qw.dis<we.dis;
} dd ans_cost,last;
int main()
{
scanf("%lf%lf%lf%lf%d",&all_dis,&capa,&per_dis,&st_p,&n);
s[].p=st_p;
for(int i=;i<=n;i++)
{
scanf("%lf%lf",&s[i].dis,&s[i].p);
}
s[n+].dis=all_dis;
for(int i=;i<=n;i++)
{
if(s[i+].dis-s[i].dis>capa*per_dis)
{
printf("No Solution\n");
return ;
}
} sort(s+,s+n+,cmp);
for(int i=;i<=n+;)
{
int j,k;
for(j=k=i+;j<=n;j++)
{
k=(s[j].p<=s[k].p?j:k);
if(s[j].p<=s[i].p||(s[j+].dis-s[i].dis)>capa*per_dis) break;
}
if(s[j].p>s[i].p)
{
ans_cost+=(capa-last)*s[i].p;
last=capa-((s[k].dis-s[i].dis)/per_dis);
i=k;
}
else
{
ans_cost+=((s[j].dis-s[i].dis)/per_dis-last)*s[i].p;
last=;
i=j; }
}
printf("%.2lf",ans_cost);
return ;
}

最新文章

  1. css 取消默认的padding
  2. 小甲鱼PE详解之IMAGE_OPTIONAL_HEADER32 结构定义即各个属性的作用(PE详解03)
  3. CSS3_loading效果
  4. 无法解析此远程名称: &#39;www.***.com&#39; 解决办法 请求因 HTTP 状态 417 失败
  5. C#导入EXCEL数据
  6. 【转】删除已经存在的 TFS Workspace
  7. Ruby on Rails Tutorial 第六章 用户模型
  8. 条形图(diagrams)
  9. MAC使用GITHUB
  10. JDBC基础学习(六)&mdash;数据库连接池
  11. [leetcode-561-Array Partition I]
  12. (一)Knockout 计算属性
  13. yield的表达式形式与内置函数
  14. 浅谈文件断点续传和WebUploader的基本结合
  15. 艾妮记账本Web开发(开发版)
  16. VC++异常处理
  17. XCode 7.3.1(dmg) 官方直接下载地址(离线下载)
  18. git配置gitignore
  19. JS封装简单后代选择器
  20. Linux - 时间相关命令 - ntpdate, date, hwclock

热门文章

  1. .NET子页Main页面实例(UI页面)
  2. WebAPI 之问题记录
  3. 广州CBC2019
  4. NEST 根据id查询
  5. MVC模式和Maven项目构建
  6. 返璞归真——OO第四单元总结暨学期总结
  7. 蓝牙 BLE 三种 UUID 格式转换
  8. python内置异常层次
  9. django获取数据queryset中的filter选项
  10. (备忘)解决用Xftp向CentOS7 传文件速度慢的问题