当前位置:网站首页>PAT甲级 1033 To Fill or Not to Fill
PAT甲级 1033 To Fill or Not to Fill
2022-07-06 02:11:00 【九是否非随机的称呼】
属于较难的题目,贪心方式要次次遍历,找后续oil station里价格最低的存在,若是不存在相对目前更低的,就是直接加满;若是存在相对更低的,去更低的地方
加满以后可能找到价格更低的地方,要减去oil bank剩的oil用距离表示即可
保证oil tank里的oil价格是最低的
#include<iostream>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
typedef struct _gas{
float price;
float dis;
int items;
}gas;
bool compare(const gas &c, const gas &b){
if(c.dis < b.dis) return true;
else return false;
}
int main(int argc, char **argv){
int m, n, i, j, h, w, e, r, t;
float mon, z, x, y;
cin>>x>>y>>z>>m;
vector<gas> v;
gas gs;
for(i = 0; i < m; i++){
cin>>gs.price>>gs.dis;
v.push_back(gs);
}
sort(v.begin(), v.end(), compare);
v.erase(v.begin() + i, v.end());
gs.price = 0;
gs.dis = y;
v.push_back(gs);
for(i = 0; i < v.size(); i++){
v[i].items = i;
}
vector<float> rem, k;
rem.push_back(0);
mon = 0;
k.push_back(0);
if(v[0].dis > 0) {
printf("The maximum travel distance = 0.00");
return 0;
}
i = 0;
float minmin, allprice = 0, lefdis = 0;
gs = v[0];
while(gs.dis < y){
float maxdis = gs.dis + x * z, flags=0;
if(maxdis < v[gs.items + 1].dis){
printf("The maximum travel distance = %.2f", maxdis);
return 0;
}
gas mingss = {999999, 0.0, -1};
for(i = gs.items + 1; i <= m && v[i].dis <= maxdis; i++){
if(v[i].dis <= gs.dis) continue;
if(v[i].price < gs.price){
allprice += (float)((v[i].dis - gs.dis - lefdis)/(float)z) * gs.price;
gs = v[i];
lefdis = 0.0;
flags = 1;
break;
}
if(v[i].price < mingss.price){
mingss = v[i];
}
}
if(flags==0){
allprice += (float)(x - lefdis/z) * gs.price;
lefdis = maxdis - mingss.dis;
gs = mingss;
}
}
printf("%.2f", allprice);
return EXIT_SUCCESS;
}
边栏推荐
- Audio and video engineer YUV and RGB detailed explanation
- Know MySQL database
- Initialize MySQL database when docker container starts
- How to generate rich text online
- 正则表达式:示例(1)
- I like Takeshi Kitano's words very much: although it's hard, I will still choose that kind of hot life
- Ali test Open face test
- 竞价推广流程
- Computer graduation design PHP enterprise staff training management system
- 【coppeliasim】高效传送带
猜你喜欢
Tensorflow customize the whole training process
插卡4G工业路由器充电桩智能柜专网视频监控4G转以太网转WiFi有线网速测试 软硬件定制
同一个 SqlSession 中执行两条一模一样的SQL语句查询得到的 total 数量不一样
Multi function event recorder of the 5th National Games of the Blue Bridge Cup
Spark accumulator
Minecraft 1.18.1、1.18.2模组开发 22.狙击枪(Sniper Rifle)
0211 embedded C language learning
Concept of storage engine
vs code保存时 出现两次格式化
selenium 等待方式
随机推荐
Paper notes: limit multi label learning galaxc (temporarily stored, not finished)
Audio and video engineer YUV and RGB detailed explanation
SPI communication protocol
729. 我的日程安排表 I / 剑指 Offer II 106. 二分图
RDD conversion operator of spark
Using SA token to solve websocket handshake authentication
Unity learning notes -- 2D one-way platform production method
leetcode3、实现 strStr()
2022年版图解网络PDF
leetcode3、實現 strStr()
Computer graduation design PHP college classroom application management system
竞价推广流程
National intangible cultural heritage inheritor HD Wang's shadow digital collection of "Four Beauties" made an amazing debut!
729. My schedule I / offer II 106 Bipartite graph
Have a look at this generation
[coppeliasim] 6-DOF path planning
Leetcode3. Implement strstr()
同一个 SqlSession 中执行两条一模一样的SQL语句查询得到的 total 数量不一样
插卡4G工业路由器充电桩智能柜专网视频监控4G转以太网转WiFi有线网速测试 软硬件定制
NumPy 数组索引 切片