[编程题]To Fill or Not to Fill (25)
- 热度指数：3002 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
With highways available, driving a car from Hangzhou to any other city
is easy. But since the tank capacity of a car is limited, we have to
find gas stations on the way from time to time. Different gas station
may give different price. You are asked to carefully design the
cheapest route to go.
输入描述:
Each input file contains one test case. For each case, the first line contains 4 positive numbers: Cmax (<= 100), the maximum capacity of the tank; D (<=30000), the distance between Hangzhou and the destination city; Davg (<=20), the average distance per unit gas that the car can run; and N (<= 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: Pi, the unit gas price, and Di (<=D), the distance between this station and Hangzhou, for i=1,...N. All the numbers in a line are separated by a space.
输出描述:
For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print "The maximum travel distance = X" where X is the maximum possible distance the car can run, accurate up to 2 decimal places.
示例1
输入
50 1300 12 8<br/>6.00 1250<br/>7.00 600<br/>7.00 150<br/>7.10 0<br/>7.20 200<br/>7.50 400<br/>7.30 1000<br/>6.85 300
输出
749.17
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
double tank = in.nextInt();
double totalTank = tank;
double distance = in.nextDouble();
double avg = in.nextDouble();
int stations = in.nextInt();
TreeSet<Station> set = new TreeSet<Station>();
for(int i = 0;i<stations;i++){
set.add(new Station(in.nextDouble(), in.nextInt()));
}
set.add(new Station(Double.MAX_VALUE,distance));
Queue<Pair> queue = new PriorityQueue<Pair>();
Iterator<Station> it = set.iterator();
Station lastStation = it.next();
queue.add(new Pair(lastStation.price, totalTank));
double totalPrice = 0.0;
double totalDistance = 0.0;
double eps=1e-6;
while(it.hasNext()){
Station cur = it.next();//
double needDis = cur.dis-lastStation.dis;//需要走的距离
Iterator<Pair> pairIt = queue.iterator();//遍历油箱
while(pairIt.hasNext()&&needDis>0){
double needGas = needDis/avg;//需要的汽油
Pair pair = pairIt.next();//
double canRun = pair.gas*avg;//能走的距离
if(canRun>=needDis){
totalPrice += needGas*pair.price;//
if(canRun==needDis){
tank -= pair.gas+eps;//
pair.gas = 0;//
}else{
tank -= needGas+eps;//总油箱减去花费的汽油
pair.gas -= needGas;//
}
totalDistance += needDis;
needDis=0;
//走完 开始换油
if(pair.price>=cur.price){
queue.clear();
queue.add(new Pair(cur.price, totalTank));
tank = totalTank;//加满
}else{
//遍历pair找到比当前油价贵的 换掉
while(pairIt.hasNext()){
pair = pairIt.next();
if(pair.price>=cur.price){
tank -= pair.gas+eps;
pairIt.remove();//
}
}
if(tank<totalTank){
queue.add(new Pair(cur.price, totalTank-tank+eps));//
tank = totalTank;//加满
}
}
break;
}else{
//当前的pair不能走到下一站
totalPrice += pair.gas*pair.price;//
tank -= pair.gas + eps;//
needDis-=canRun;//需要走的距离减去可以走的距离
totalDistance += canRun;
pairIt.remove();//移除当前pair
}
}
if(needDis>0){
System.out.printf("The maximum travel distance = %.2f\n",totalDistance);
return;
}
lastStation = cur;
}
System.out.printf("%.2f\n",totalPrice);
}
private static class Station implements Comparable<Station>{
double price;
double dis;
public Station(double price, double dis) {
this.price = price;
this.dis = dis;
}
@Override
public int compareTo(Station o) {
if(this.dis>o.dis)
return 1;
else if(this.dis==o.dis)
return (int)(this.price-o.price);
return -1;
}
}
private static class Pair implements Comparable<Pair>{
double price;
double gas;
public Pair(double price, double gas) {
this.price = price;
this.gas = gas;
}
@Override
public int compareTo(Pair o) {
if(this.price>o.price)
return 1;
else if(this.price==o.price)
return 0;
return -1;
}
}
}
编辑于 2016-07-23 17:57:18
回复(0)
更多回答
#include <iostream>
#include <algorithm>
using namespace std;
struct station{
double price,dis; //每个加油站的价格与起点距离
}s[510];
bool cmp(station a,station b){
return a.dis<b.dis; //将加油站按距离从小到大排序
}
const long long MIN=100000000;
int main(){
int n;double cmax,distance,davg; //除了加油站个数外其他数据都可能不是整数，用浮点型
cin>>cmax>>distance>>davg>>n;
for(int i=0;i<n;i++)
cin>>s[i].price>>s[i].dis;
sort(s,s+n,cmp);
s[n].price=0;
s[n].dis=distance; //设置一个终点站
if(s[0].dis!=0) printf("The maximum travel distance = 0.00\n"); //起点没有加油站，无法出发
else{
int now=0;
double max=cmax*davg,sum=0,nowc=0; //now为当前加油站编号，max为一箱油能跑多远，sum为累积油钱，nowc为当前油箱油量
while(now<n){
int k=-1;double minprice=MIN; //k为最低油价的加油站编号
for(int i=now+1;i<=n&&s[i].dis-s[now].dis<=max;i++){ //选择从当前加油站出发能到达的范围内第一个低于当前油价的加油站，没有的话就选范围内最低的一个
if(s[i].price<minprice){
minprice=s[i].price;
k=i;
if(minprice<s[now].price) break; //找到第一个低于当前油价的加油站，直接退出循环
}
}
if(k==-1) break; //范围内没有加油站
double need=(s[k].dis-s[now].dis)/davg; //need为从当前出发到达目标加油站所需油量
if(minprice<s[now].price){ //若目标加油站油钱低于当前加油站
if(need>nowc){ //若当前油量不够直接跑到目标加油站
sum+=(need-nowc)*s[now].price;
nowc=0; //加到可到目标加油站的油量，到达后油箱刚好用完
}
else
nowc-=need; //若当前油量超过所需油量，不加油直接跑到下个加油站
}
else{
sum+=(cmax-nowc)*s[now].price; //若目标加油站油价高于当前加油站，则在当前油站先加满油更划算
nowc=cmax-need;
}
now=k; //到达目标油站，更新当前油站编号
}
if(now==n) printf("%.2f\n",sum); //能到终点，输出总油钱
else printf("The maximum travel distance = %.2f\n",s[now].dis+max); //不能到达终点，输出最远距离
}
return 0;
}
发表于 2018-01-27 18:56:23
回复(0)
//贪心：先按照加油站距离升序排序，然后采取如下贪心策略：
/*从当前所在加油站向后找（装满油能达到的范围内找），
*如果有花费更少的的加油站x1，则加油加到能到达x1为止；
*如果范围内的加油站花费都大，则加满油。
*途中更新剩余油量，以及到达距离。
*注意精度问题，剩余油量小于0不一定是无法到达，
*因为精度的原因，在一定范围内，可以允许油量小于0（我设置的允许范围是10^(-10)）.
*/
#include <bits/stdc++.h>
#define inf 1e-10 // 允许的误差范围
using namespace std;
const int AX = 5e2 + 66 ;
struct Node {
double p , d ;
bool operator < ( const Node & x )const {
return d < x.d ;
}
} a[AX];
int main() {
double V , d , x; int n ;
scanf("%lf%lf%lf%d",&V,&d,&x,&n);
for( int i = 0 ; i < n ; i++ ) {
scanf("%lf%lf",&a[i].p,&a[i].d);
}
a[n++].d = d ;
double res = 0.0 , dis = 0.0 , left = 0.0 ;
sort( a , a + n );
int f = 0 ;
for( int i = 0 ; i < n ; i++ ) {
if( i ) f = 1 ; //走过距离是否为0
int id = i ;
left -= ( a[i].d - ( ( !i ) ? 0.0 : a[i-1].d ) ) / x ;
if( a[i].d == d ) { dis = d ; break ; }
if( left < 0 ) {
if( 0-left > inf ) {
dis = ( ( !i ) ? 0.0 : a[i-1].d ) ; //超过允许的范围，则不可达
break ;
} else left = 0 ; //油量用光
} else dis = a[i].d;
for( int j = i + 1 ; j < n ; j++ ) {
if( a[j].d > d ) break ;
if( V * x >= a[j].d - a[i].d ) { //可达范围内寻找花费比自己少的加油站
if( a[j].p < a[i].p ) {
id = j ;
break ;
}
} else break ;
id = j ;
}
if( a[id].p < a[i].p ) { //花费少更新油量为能达到此加油站
double ned = ( a[id].d - a[i].d ) / x ;
if( ned > left ) {
res += ( ned - left ) * a[i].p ;
left = ned ;
}
} else { //范围内没有花费更少的则加满油
res += ( V - left ) * a[i].p ;
left = V ;
}
}
if( dis < d ) {
if( f ) printf("The maximum travel distance = %.2lf",dis+V*x);
else printf("The maximum travel distance = 0.00");
} else {
printf("%.2lf",res);
}
return 0 ;
}
编辑于 2020-03-03 17:01:14
回复(0)
解法是参考某c++的解法，原链接：https://www.cnblogs.com/XBWer/p/3866486.html
但是java有些测试样例无法通过，个人认为是double精度问题。
暂时不知道如果解决，如果知道解决方法，欢迎留言讨论
package go.jacob.day1129; import java.text.DecimalFormat; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; /* * 处在当前加油站（起点加油站）的情况下 * 情况1：600米范围内，有目的地——计算恰好能到目的地的油量 * 情况2：600米范围内没有加油站，无论油价多贵——加满——能跑多远算多远 * 情况3：600米范围内有加油站： * a:有比当前加油站的油价更便宜的加油站——加到恰好能到那个最近的油站的油量 * （注：1、如果有多个便宜的，还是要先选取最近的那个，而不是最便宜的那个；2、可能还有油剩余） * b:没有比当前加油站的油价更便宜的加油站——加满，然后在600范围内找到最便宜的加油站加油 */ /** * 参考解法：https://www.cnblogs.com/XBWer/p/3866486.html * * @author Administrator 贪心算法求解 */ public class Demo2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); double tank = sc.nextDouble(), distance = sc.nextDouble(), avgDist = sc.nextDouble(); int n = sc.nextInt(); List<Station> list = new ArrayList<Station>(); for (int i = 0; i < n; i++) { Station s = new Station(sc.nextDouble(), sc.nextInt()); list.add(s); } sc.close(); Collections.sort(list); // 特殊情况：1.目的地址为原点；2.原点没有加油站 if (distance == 0) { System.out.println("0.00"); return; } if (list.get(0).getDist() != 0) { System.out.println("The maximum travel distance = 0.00"); return; } int curStNum = 0;// 当前所处加油站编号 double curGas = 0;// 当前的油量 double curCost = 0;// 当前花费 boolean flag = false;// 是否可以到达目的地 double maxDis = tank * avgDist; while (!flag) { boolean tag = false;// 最大距离内是否有加油站 boolean ifCheaper = false;// 是否有便宜的 double cheapestPrice = 10000;// 找出最便宜的 int cheapestNum = 0;// 没有更便宜的情况下，找出最便宜的 for (int i = curStNum + 1; i < n; i++) { // 在可达范围内有加油站 if ((list.get(i).getDist() - list.get(curStNum).getDist()) <= maxDis) { tag = true;// 有加油站 if (list.get(i).getPrice() < list.get(curStNum).getPrice()) {// 情况3-a:在可达范围内有比当前更便宜的加油站 ifCheaper = true; double dist = list.get(i).getDist() - list.get(curStNum).getDist(); double needGas = dist / avgDist - curGas; curGas = 0; curCost += needGas * list.get(curStNum).getPrice(); curStNum = i; break; } } if (list.get(i).getPrice() < cheapestPrice) { cheapestPrice = list.get(i).getPrice(); cheapestNum = i; } else// 范围内没有加油站 break; } // 说明已经可以到达目的地了,情况1 if (!ifCheaper && (distance - list.get(curStNum).getDist() <= maxDis)) { double dist = distance - list.get(curStNum).getDist(); double needGas = dist / avgDist - curGas; curCost += needGas * list.get(curStNum).getPrice(); System.out.printf("%.2f", curCost); return; } if (tag && !ifCheaper) {// 情况3-b：没有比当前加油站的油价更便宜的加油站——加满，然后在600范围内找到最便宜的加油站加油 double needGas = tank - curGas; curCost += (needGas * list.get(curStNum).getPrice()); double dist = list.get(cheapestNum).getDist() - list.get(curStNum).getDist(); curGas = tank - dist / avgDist; curStNum = cheapestNum; } else if (!tag) { System.out.print("The maximum travel distance = "); System.out.printf("%.2f", list.get(curStNum).getDist() + maxDis); return; } } } /* * 加油站类 */ static class Station implements Comparable<Station> { private double price; private double dist; public Station(double price, double dist) { super(); this.price = price; this.dist = dist; } @Override public int compareTo(Station s1) { return this.dist - s1.getDist() < 0 ? -1 : 1; } public double getPrice() { return price; } public double getDist() { return dist; } } }
发表于 2017-11-29 12:23:33
回复(1)
a = list(map(int,input().split()))
b = sorted([list(map(eval,input().split())) for i in range(a[3])],\
key = lambda x: x[1]) + [[-1,a[1]],[float('inf'),0]]
if b[0][1] != 0:
print('The maximum travel distance = 0.00')
import sys;sys.exit(0)
i,m,n = 0,b[0] + [0],[]
while i < a[3]:
j,q = i + 1,a[3] + 1
while b[j][1] - m[1] <= a[0] * a[2]:
if b[j][0] < m[0]:
n.append([b[i][0],b[j][1] - sum(m[1:])])
q = j
break
if b[j][0] < b[q][0]:
q = j
j += 1
else:
if b[q][1]:
n.append([b[i][0],a[0] * a[2] - m[2]])
else:
print('The maximum travel distance = {:.2f}'.\
format(m[1] + a[0] * a[2]))
break
i,m = q,b[q] + [sum(m[1:]) + n[-1][1] - b[q][1]]
else:
print('{:.2f}'.format(sum([i[0] * i[1] for i in n]) / a[2]))
编辑于 2020-03-11 16:59:10
回复(0)
思路：
(1)首先对所有加油站按距离排序，设置加满油箱可行驶的最大距离为max_dis，当前的位置cur_dis
(2)从cur_dis 到cur_dis+max_dis这个距离范围内找比当前加油站价格更便宜的第一个加油站s1, 当前加的油量为刚好到s1
(3)若(2)中没有找到，则从从cur_dis 到cur_dis+max_dis中找到最便宜的那个加油站s2，并且在当前站加满油量
循环操作就行
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
using namespace std;
const int maxn = 501;
struct Station {
double price;
int dis;
};
Station stations[maxn];
int Cmax, D, Davg, N;
bool cmp(Station a, Station b) {
if(a.dis != b.dis)
return a.dis<b.dis;
else
return a.price<b.price;
}
int find_next_station(int cur_station, int cur_dis, double cur_price, int max_dis) {
int next_station = -1;
for(int i=cur_station+1; i<N; i++) {
if(stations[i].dis<=cur_dis+max_dis && stations[i].dis<D) {
if(stations[i].price<=cur_price) {
next_station = i;
break;
}
} else {
break;
}
}
if(next_station == -1) {
double min_price = 99999999;
for(int i=cur_station+1; i<N; i++) {
if(stations[i].dis<=cur_dis+max_dis && stations[i].dis<D) {
if(stations[i].price<=min_price) {
next_station = i;
min_price = stations[i].price;
}
} else {
break;
}
}
}
return next_station;
}
int main() {
scanf("%d %d %d %d", &Cmax, &D, &Davg, &N);
for(int i=0; i<N; i++) {
scanf("%lf %d", &stations[i].price, &stations[i].dis);
}
sort(stations, stations+N, cmp);
int max_dis = Cmax * Davg; /**加满油箱后能行走的最大距离*/
double cur_gas = 0; /**当前有油箱中剩余的油量*/
int cur_dis = 0, cur_station = 0, next_station = 0;
double cur_price = stations[0].price; /**当前加油站的价格*/
if(stations[0].dis>0) {
printf("The maximum travel distance = 0.00");
return 0;
}
double total_cost = 0;
while(next_station != -1) {
next_station = find_next_station(cur_station, cur_dis, cur_price, max_dis);
//cout<<next_station<<endl;
if(next_station != -1) {
if(stations[next_station].price <= cur_price) { /**如果在可行驶最大距离中存在价格更便宜的s1，则加的油只需要刚好能到s1就行*/
total_cost += ((double)(stations[next_station].dis - cur_dis)/Davg-cur_gas) * cur_price;
cur_gas = 0;
cur_dis = stations[next_station].dis;
cur_price = stations[next_station].price;
} else { /**否则，在当前站加的油需要加到最大*/
if(cur_dis + max_dis <= D) { /**当前加满可走的距离未到重点，加满油箱*/
total_cost += (Cmax-cur_gas)*cur_price;
cur_gas = Cmax - (double)(stations[next_station].dis - cur_dis)/Davg;
cur_dis = stations[next_station].dis;
cur_price = stations[next_station].price;
} else { /**当前加满可走到终点，则只需加到刚到终点的油量就行*/
total_cost += ((double)(D - cur_dis)/Davg-cur_gas) * cur_price;
cur_gas = 0;
cur_dis = stations[next_station].dis;
cur_price = stations[next_station].price;
printf("%.2f",total_cost);
return 0;
}
}
cur_station = next_station;
} else { /**找不到可到达下一个的加油站*/
if(cur_dis + max_dis <= D) { /**如果在当前加油站加满也无法到达，则最终不能到达*/
total_cost += (Cmax-cur_gas)*cur_price;
cur_dis += max_dis;
printf("The maximum travel distance = %.2f", (double)cur_dis);
return 0;
} else { /***/
total_cost += ((double)(D - cur_dis)/Davg-cur_gas) * cur_price;
printf("%.2f",total_cost);
return 0;
}
}
}
}
发表于 2019-08-30 16:41:25
回复(0)
因为那个贪心算法的思路讲的太乱了，我就没仔细看 别人说算法很好应该效率蛮高的 这里贴一个相对容易理解的算法
思路就是模拟人的思维：
读入后按距离给加油站排序以便后续访问
0.如果当前位置当前油量可以到终点了，返回当前花费
1.找到从当前位置能开到的价格最低的加油站
2.如果最优站是当前站且能直接开到终点，返回之前花费和还需要加的汽油钱
3.如果最优站是当前站但不能开到终点，加满油开到下一站
4.如果油量够到最优站，开到最优站
5.如果当前站和最优站中间有较优站(比当前站便宜)，油够开过去，不够加到够再过去
6.（中间没有较优站）加够油开到最优站
代码稍微麻烦了点，但效率应该不算低
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct Station{
int Dis;
double Price;
};
inline bool cmp(Station A, Station B) { return A.Dis < B.Dis; }
Station station[500];
double Cmax, Davg;
int D, N, dis = 0;
double go(double tank, int idx) {
static double count = 0;
static double Max = Cmax * Davg;
if (dis + tank * Davg >= D) {
dis = D;
return count; // 走到了
}
double nowPrice = station[idx].Price;
double lowPrice = nowPrice;
int pos = idx, p = idx + 1;
while (p < N) {
if (Max > station[p].Dis - dis) {
if (station[p].Price < lowPrice) {
pos = p;
lowPrice = station[pos].Price;
}
}
else break;
p++;
}
if (lowPrice == nowPrice) {
if (Max + dis > D) { // 可以到了，加到够走到
int len = D - dis;
double c = len / Davg;
dis = D;
return count + (c - tank)*nowPrice;
}
count += (Cmax - tank)*nowPrice;
if (idx + 1 >= N || Max + dis < station[idx + 1].Dis) { // 走不到了，加满走到哪是哪
dis += Max;
return count;
}
int len = station[idx + 1].Dis - dis;
double c = len / Davg;
dis = station[idx + 1].Dis;
return go(Cmax - c, idx + 1); // 加满，走到下一站
}
int len = station[pos].Dis - dis;
double c = len / Davg;
if (c <= tank) {
dis = station[pos].Dis;
return go(tank - c, pos); // 不加油，走到最优站
}
for (int i = idx + 1;i < pos;i++) { // 油不够到最优站
if (station[i].Price < nowPrice) {
int len = station[i].Dis - dis;
dis = station[i].Dis;
double c = len / Davg;
if (c <= tank)return go(tank - c, i); // 不加油，走到中间站加油
count += (c - tank)*nowPrice;
return go(0, i); // 加油到中间站再加油
}
}
dis = station[pos].Dis;
count += (c - tank)*nowPrice;
return go(0, pos);
}
int main(int argc, const char* argv[]) {
ios::sync_with_stdio(false);
cin >> Cmax >> D >> Davg >> N;
for (int i = 0;i < N;i++) cin >> station[i].Price >> station[i].Dis;
sort(station, station + N, cmp);
while (station[N - 1].Dis >= D)N--;
if (station[0].Dis) {
cout << "The maximum travel distance = 0.00";
//system("pause");
return 0;
}
double count = go(0, 0);
if (dis - D)printf("The maximum travel distance = %.2f", (float)dis);
else printf("%.2f", count);
//system("pause");
return 0;
}
发表于 2017-02-17 18:09:06
回复(0)
#include <iostream>
#include <algorithm>
using namespace std;
struct station
{
double distance;
double price;
bool operator<(const station &t)const {
return distance < t.distance;
}
};
station tem[505];
int main()
{
double tank, distance, oil;
int num;
double price = 0, maxdistance = 0,max = 0;
cin >> tank >> distance >> oil >> num;
max = oil * tank;
if (tank == 0 || oil == 0)
return -1;
for (int i = 0; i < num; i++)
{
scanf("%lf %lf", &tem[i].price, &tem[i].distance);
}
sort(tem, tem + num);
tem[num].distance = distance;
tem[num].price = 0;
//pat1033中有个case需要加此判断
if (tem[0].distance != 0) {
cout << "The maximum travel distance = 0.00\n";
return 0;
}
double currentdistance = 0;
double currentprice = tem[0].price;
double left = 0;
double totalprice = 0;
int smallest = 0;
int start = 0;
for (int i = 0; i <= num; i++) {
if (currentdistance + max < tem[i].distance) {
if (start == 0) {
break;
}
totalprice += (tank - left) * currentprice;
left = (tank - (tem[smallest].distance - currentdistance) / oil);
currentdistance = tem[smallest].distance;
currentprice = tem[smallest].price;
i = smallest;
start = 0;
continue;
}
if (tem[i].price <= currentprice) {
totalprice += ((tem[i].distance - currentdistance) / oil - left) * currentprice;
currentdistance = tem[i].distance;
currentprice = tem[i].price;
if (currentdistance == distance) {
break;
}
left = 0;
start = 0;
}
else {
if (tem[i].price < tem[smallest].price || start == 0) {
start = 1;
smallest = i;
}
}
}
cout.setf(ios::fixed);
cout.precision(2);
if (currentdistance == distance) {
cout << totalprice;
}
else {
cout << "The maximum travel distance = " << currentdistance + max;
if (currentdistance + max == distance)
return -1;
}
return 0;
}
发表于 2016-08-12 13:21:02
回复(0)
某个野路子计算方法。简单粗暴。。。。
将路程看成一段一段的，每一公里的单价是一样的，设置一个足够长的数组，记录每一公里的单价，初始值为-1，将加油站按单价的从高到低排序，然后依次将每个加油站后面Cmax*Davg长的线路的单价赋值为该加油站的单价，这样到最后就得到了每一公里最少的单价，然后从前向后遍历，如果某一公里的单价为-1就表示无法到达，对每一公里的单价/Davg求和就得到了最低的价格。
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;
struct tank {
double price;
int dis;
};
bool cmp(tank t1,tank t2) {
return t1.price > t2.price;
}
double pri[30010] = {0};
vector<tank> ts;
int Cmax, D, Davg, N;
int main() {
cin >> Cmax >> D >> Davg >> N;
ts.resize(N);
for (int i = 0; i < N;i++) {
cin >> ts[i].price;
cin >> ts[i].dis;
}
sort(ts.begin(), ts.end(), cmp);
for (int i = 0; i < D; i++) {
pri[i] = -1;
}
for (int i = 0; i < N;i++) {
for (int j = ts[i].dis; j < ts[i].dis + Cmax*Davg&&j<D;j++) {
pri[j] = ts[i].price;
}
}
double sum=0;
int i = 0;
for (i = 0; i < D; i++) {
if (pri[i] < 0) {
break;
}
sum += pri[i];
}
if (i >= D)
printf("%.2lf", sum/Davg);
else
printf("The maximum travel distance = %d.00", i);
return 0;
}
发表于 2019-09-03 15:40:37
回复(0)
贪心问题，当前站加油加到下一个价格比它小的站。如果在加满能够到达的范围内这个站不存在，则加满。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int M = 105;
const int N = 505;
int n, m, effort, ed;
struct Node {
double price;
int dist;
bool operator<(const Node& node) const { return dist < node.dist; }
} station[N];
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cin >> m >> ed >> effort >> n;
for (int i = 1; i <= n; i++) {
cin >> station[i].price >> station[i].dist;
}
int endurance = m * effort;
n++;
station[n] = {0, ed}; // 终点
station[0] = {0, 0}; // 起点
sort(station + 1, station + n + 1);
int left = 0;
double reach = 0;
double cost = 0;
bool success = true;
for (int i = 1; i <= n; i++) {
left -= station[i].dist - station[i - 1].dist;
if (left < 0) {
success = false;
break;
}
int p = i + 1;
while (station[p].dist - station[i].dist <= endurance &&
station[p].price > station[i].price) {
p++;
}
if (station[p].dist - station[i].dist > endurance) {
cost += (double)(endurance - left) * station[i].price / effort;
left = endurance;
reach = station[i].dist + endurance;
} else {
int delta = station[p].dist - station[i].dist;
if (left < delta) {
cost += (double)(delta - left) * station[i].price / effort;
left = delta;
}
}
}
if (success)
cout << setprecision(2) << fixed << floor(cost * 100 + 0.5) / 100 << endl;
else
cout << "The maximum travel distance = " << setprecision(2) << fixed
<< reach;
return 0;
}
发表于 2022-08-24 23:51:53
回复(0)
#include<iostream>
#include<algorithm>
using namespace std;
struct Station{
double Pi;
double Di;
};
bool Compare(Station a, Station b){
if(a.Di==b.Di) return a.Pi<b.Pi;
else return a.Di < b.Di;
}
int find(double Cmax){
double D, Davg;
int N;
Station station[510];
cin>>D>>Davg>>N;
for(int i=0;i<N;i++) cin>>station[i].Pi>>station[i].Di;
sort(station, station+N, Compare);
double Position = 0, Price = 0, nowPrice = station[0].Pi, remainC = 0;
int nowIndex = 0;
while(Position < D){
if(nowIndex==N-1){//后面没有加油站了，不找
if(Position+Cmax*Davg>=D){
Price+=((D-Position)/Davg-remainC)*nowPrice;
printf("%.2f\n",Price);
}else{
printf("The maximum travel distance = %.2f\n", Position+Cmax*Davg);
}
return 0;
}
//后面至少还有一个加油站，找最便宜的或者第一个更便宜的
int i = nowIndex+1;
double minPi = 100000000, minDi = 0;
int minIndex = 0;
while(i<N && station[i].Di-Position<=Cmax*Davg){
if(station[i].Pi <= nowPrice){//找到第一个小的
minPi = station[i].Pi;
minDi = station[i].Di;
minIndex = i;
break;
}else{//找到所有范围内最小的
if(station[i].Pi < minPi){
minPi = station[i].Pi;
minDi = station[i].Di;
minIndex = i;
}
i++;
}
}
if(station[nowIndex+1].Di - Position > Cmax * Davg){//找不到，也就是去不了
printf("The maximum travel distance = %.2f\n", Position+Cmax*Davg);
return 0;
}
//找到小的直接去点
if(minPi <= nowPrice){
Price+=((minDi - Position)/Davg - remainC)* nowPrice;
remainC = 0;
Position = minDi;
nowPrice = minPi;
nowIndex = minIndex;
}else{//找到大的看能不能直接去终点。
if(Cmax*Davg>D-Position){//能去终点直接去
Price += ((D-Position)/Davg - remainC)*nowPrice;
printf("%.2f\n",Price);
return 0;
}else{//不能去终点去下个点
Price += (Cmax - remainC)*nowPrice;
remainC = Cmax - (minDi - Position) / Davg;
Position = minDi;
nowPrice = minPi;
nowIndex = minIndex;
}
}
}
}
int main(){
double Cmax;
while(cin>>Cmax){
find(Cmax);
}
return 0;
} 做了四个小时。。。必须记录下我出错的过程。。。思路是贪心算法，从每次加油站出发找到最便宜的路，要么去加油站，要么去终点，要么都去不到。
这个题目感觉思路倒不难，一条路，很多个加油站。将车加一次油作为一次阶段，每个阶段都找到最便宜的路，总体也是最便宜的。
首先假设车在某个加油站，开始往后走，需要考虑现在加多少油合适。会存在2种情况：
1）不需要查看后面的加油站的价格，当前加油站是最后一个，后面只有终点了。此时要看能不能走到终点，能走到就加刚好够用的油，计算并输出价格，不能走到就加满油输出能走的路程。
2）需要查看后面的加油站的价格。这种情况下还存在三种情况：
1.找不到后面能去的加油站，最近的加油站也超过了车能去的范围。这种情况直接加满油，输出路程。
2.找到了更便宜的加油站，那肯定尽可能去更便宜的加油站，只要把油加到够用到更便宜的加油站就行；到达更便宜的加油站就开始下一次判断。
3.找不到更便宜的加油站，后面的加油站都比现在贵，后面最便宜的加油站也比当前的加油站要贵，那肯定要在现在把油尽可能多加。“后面”这个范围最大多少呢？就是车加满油能走的范围，前面说了每次判断车加一次油的运动，所以只能在这个范围内。超过这个范围车去不到。这时如果车能去终点，那直接把油加到够用到终点就行，不用加满；如果去不了终点，那肯定要把油加满，后面的加油站更贵，加满之后去到其中最便宜的加油站进行下一次判断。
总结下原因，主要还是各种情况的分类不合理，导致一直死循环，还有float和double精度的问题，以后一定要用double。
发表于 2021-05-30 23:13:46
回复(0)
#include<bits/stdc++.h>
using namespace std;
#define eps 1e-8
const int N=501;
/*
贪心
关键在于如何选择下一个汽油站
设加满油的情况下 能跑的最大距离为maxd (maxd=capacity*avg)
那么如果在当前位置的最大距离内 没有其他加油站
那肯定走不动了 GG
否则，从这些可达的加油站里，挑选第一个油价比自己低的
这样就能最快的用到比较低价的油
如果可达的汽油站 油价都比自己高 那肯定在当前位置我要把油加满
然后跑到这些新汽油站里燃油价格最低的那个
特判就是如果自己是可达位置里价格最低的加油站(最后一个加油站)
那直接到终点
所以在过程中我们维护花费的钱res 当前位置i 到达位置i之后的燃油数量cur
注意如果燃油价格相等 那我们肯定贪心的选择更远的加油站
*/
struct node{
double p,d;
}a[N];
bool cmp(node A,node B){
return A.d<B.d;
}
int main()
{
int n;
double capacity,D,avg;
cin>>capacity>>D>>avg>>n;
for(int i=0;i<n;i++){
cin>>a[i].p>>a[i].d;
}
sort(a,a+n,cmp);
a[n].d=D;
double maxd=avg*capacity;
for(int i=1;i<=n;i++){
if(a[i].d-a[i-1].d > maxd){
printf("The maximum travel distance = %.2f\n",a[i-1].d+maxd);
return 0;
}
}
double res=0,cur=0;
int i=0;
while(i<n){
//printf("cur pos is %d cur gas is %.2f cur res is %.2f\n",i,cur,res);
double mp=1e18;
int pos=-1;
for(int j=i+1;j<n;j++){
if(a[j].d - a[i].d >maxd) break;//距离太远
if(mp > a[j].p || fabs(a[j].p - mp )<eps){//燃油价格相等的话 也应该跑过去
mp=a[j].p;
pos=j;
if(mp < a[i].p || fabs(mp-a[i].p)<eps) break;
}
}
if(mp > a[i].p || fabs(mp-a[i].p)<eps){//如果可达距离内的新汽油站 燃油价格比自己高
if(a[i].d+maxd>=D){//直接跑到终点是否可行
res+=((D-a[i].d)/avg-cur)*a[i].p;
break;
}
res+=(capacity-cur)*a[i].p;
cur=capacity-(a[pos].d-a[i].d)/avg;
}
else{//跑到价格更低的新汽油站
if(cur*avg < a[pos].d-a[i].d){//当前燃油够不够
res+=a[i].p*((a[pos].d - a[i].d - cur*avg)/avg);
cur=0;
}
else{
cur-=(a[pos].d-a[i].d)/avg;
}
}
i=pos;//更新位置
}
printf("%.2f\n",res);
return 0;
}
发表于 2021-03-08 12:09:25
回复(0)
每次做这种逻辑题的时候，感觉自己像个**一样，本身又不来但是总是要debug很久，一些细节没考虑到，然后代码也很冗余，不方便读。。。。。。
//这个题要注意不能达到和可以达到目的地的情况，当某一轮循环中，如果能在范围内找到（有多个话取第一个）比当前价格更便宜的加油站，就只加刚好可以到这个加油站的gas，如果找不到，那么需要判断如果当前满油能够跑到终点，那么就加满结束，否则那么也将油加满并且找一个此范围内油费最便宜的站，将这个站作为下一站。如果找不到后续的加油站，则判断从当前加满油是否能到终点，如果不能则加满，算行驶最大距离，如果能，则加到能够到达终点就行
#include<iostream>
(720)#include<vector>
#include<algorithm>
(831)#include<limits.h>
using namespace std;
const int maxn = 100000000;
struct gasPosition {
double price;
double x;
gasPosition(double p, double x) :price(p), x(x) {}
};
bool cmp(gasPosition g1, gasPosition g2) {
if (g1.x != g2.x) {
return g1.x < g2.x;
}
return g1.price < g2.price;
}
int main() {
double full, dis, unit;
int n;
cin >> full >> dis >> unit >> n;
vector<gasPosition>gasPositions;
while (n--) {
double p, x;
cin >> p >> x;
gasPositions.push_back(gasPosition(p, x));
}
sort(gasPositions.begin(), gasPositions.end(), cmp);
double curX = 0, curGas = 0, pay = 0;
int curGasPosition = 0;
bool flag = true;
while (curX < dis&&flag) {
int next = -1;
int minIndex =-1;
double price =maxn;
for (int i = curGasPosition + 1; i < gasPositions.size() && gasPositions[i].x - curX <= unit * full; i++) {
if (gasPositions[i].price < gasPositions[curGasPosition].price) {//找到了第一个就跳出
next = i;
break;
}
if (gasPositions[i].price < price&&gasPositions[i].x>gasPositions[curGasPosition].x) {//可能会存在同一个位置有多个加油站的情况
minIndex = i;
price = gasPositions[i].price;
}
}
if (next != -1) {//说明找到了下一个比当前便宜的
double length = gasPositions[next].x - gasPositions[curGasPosition].x - curGas * unit;
pay += (length / unit) * gasPositions[curGasPosition].price;
curGasPosition = next;
curX = gasPositions[next].x;
curGas = 0;
}
else if ( minIndex != -1) {//后续找到了在后续加油站中价钱最便宜的
if (dis - gasPositions[curGasPosition].x <= full * unit) {
double length = dis - gasPositions[curGasPosition].x - curGas * unit;
pay += (length / unit) * gasPositions[curGasPosition].price;
curX = dis;
}
else {
pay += (full - curGas) * gasPositions[curGasPosition].price;
curGas = full - (gasPositions[minIndex].x - gasPositions[curGasPosition].x) / unit;
curGasPosition = minIndex;
curX = gasPositions[minIndex].x;
}
}
else if (minIndex==-1) {//后续没有加油站了//176.25
double length = dis - gasPositions[curGasPosition].x;
if (length <= full*unit) {
pay += (length / unit) * gasPositions[curGasPosition].price;
curGasPosition = next;
curX = dis;
curGas = 0;
}
else {
flag = false;
pay += (full - curGas) * gasPositions[curGasPosition].price;
curX = gasPositions[curGasPosition].x + full*unit;
}
}
}
if (flag) {
printf("%.2lf", pay);
}
else {
printf("The maximum travel distance = %.2lf", curX);
}
}
发表于 2020-03-30 18:26:27
回复(0)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
struct node { double price; double dis; bool operator < (const node &rhs) const { return dis < rhs.dis; }
}station[maxn];
int main() { std::ios::sync_with_stdio(false); double C, D, P; int N; cin >> C >> D >> P >> N; for (int i = 1; i <= N; ++i) { cin >> station[i].price >> station[i].dis; } sort(station + 1, station + 1 + N); if (station[1].dis != 0) { printf("The maximum travel distance = %.2lf\n", 0); return 0; } station[N + 1].dis = D; double mxdis = P * C; int spos = 1; double gas = 0; double cost = 0; bool flag = false; while (spos <= N) { if (station[spos].dis + mxdis < station[spos + 1].dis) { flag = true; break; } int nxp = spos; for (int i = spos + 1; station[spos].dis + mxdis >= station[i].dis && i <= N + 1; ++i) { if (station[i].price <= station[nxp].price) { nxp = i; break; } } if (nxp == spos) { cost += (C*1.0 - gas)*station[spos].price; gas = C - (station[spos+1].dis-station[spos].dis)*1.0/P; spos++; } else { double dx = station[nxp].dis - station[spos].dis; if (gas*P < dx) { double dp = dx / P - gas; cost += dp * station[spos].price; gas = 0; } else { gas -= dx / P; } spos = nxp; } } if (flag) { printf("The maximum travel distance = %.2lf\n", (station[spos].dis + mxdis)*1.0); } else { printf("%.2lf\n", cost); } return 0;
}
发表于 2019-02-01 11:52:12
回复(0)
cmax,d,davg,n = map(int,input().split())
lst1 = []
dis = cmax*davg
for i in range(n):
tem = input().split()
lst1.append([float(tem[0]),int(tem[1])])
lst1.sort(key = lambda x:(x[1],x[0]))
k = lst1[0][1]
lst = [lst1[0]]
for i in lst1:
if k!=i[1]:
lst.append(i)
k = i[1]
lst.sort(key = lambda x:(x[1],x[0]))
i,j,price,travel,boo,cleft = 0,1,0.0,0,True,0
while j<len(lst) and i<len(lst)-1 and d>0:
mi,boo1,tem1 = lst[i][0],False,[]
if lst[j][1]-lst[i][1]>dis:
print("The maximum travel distance = "+str("%.2f"%(travel+dis)))
boo= False
break
while j<len(lst) and i<len(lst)-1 and lst[j][1]-lst[i][1]<=dis:
if lst[j][0]<mi:
mi = lst[j][0]
boo1 = True
te = lst[j]
break
temp = list([j]+lst[j])
tem1.append(temp)
j+=1
if boo1:
if cleft<=te[1]-lst[i][1]:
price += lst[i][0]*(te[1]-lst[i][1]-cleft)/dis*cmax
cleft = 0
else:
cleft -=te[1]-lst[i][1]
travel+=(te[1]-lst[i][1])
d-=(te[1]-lst[i][1])
if j<len(lst):
i = int(j)
else:
break
j = i+1
if j==len(lst):
break
if lst[j][1]-lst[i][1]>dis:
print("The maximum travel distance = "+str("%.2f"%(travel+dis)))
boo= False
break
else:
if d>dis:
tem1.sort(key=lambda x:(x[1]))
price += lst[i][0]*(dis-cleft)/dis*cmax
travel+=(tem1[0][2]-lst[i][1])
cleft = dis - (tem1[0][2]-lst[i][1])
d-=(tem1[0][2]-lst[i][1])
i = int(tem1[0][0])
j = i+1
else:
price+=lst[i][0]*(d-cleft)/dis*cmax
travel+=d
d-=(lst[j-1][1]-lst[i][1])
cleft = d
i = int(j-1)
j=i+1
if boo:
price = price+(d-cleft)/dis*cmax*lst[i][0]
print("%.2f"%price)
调了好几遍，最终解决了这个问题。
思路大概是这样：
把加油站按距离前后排序，并选出同距离最便宜的加油站作为备选项。然后在汽车加满油后可以跑的距离内寻找最便宜的加油站加油，但是如果找得到比当前加油站便宜的，就先去那里再说。如果快要到终点了，就把油加到能够跑到终点就够了；如果没有的话，那就把油给加满。
发表于 2018-12-09 09:58:21
回复(0)
C,D,Dvg,N=map(int,input().split())
L=[list(map(float,input().split())) for _ in range(N)]
L.append([0,D])
L.sort(key=lambda x:x[1])
filter(lambda x:x[1]>D,L)
def tryDrive(s,gas,res):
if s==len(L)-1:
print('{:.2f}'.format(res))
return
right=min(D,L[s][1]+C*Dvg)
r=max(i if L[i][1]<=right else s for i in range(s+1,len(L)))
best=s
for i in range(s+1,r+1):
if L[i][0]<=L[s][0]:
best=i
break
if r==s:
d=L[s][1]+C*Dvg
print('The maximum travel distance = {:.2f}'.format(d))
elif best==s:
tmp,sec=min((L[i][0],i) for i in range(s+1,r+1))
cost=(L[sec][1]-L[s][1])/Dvg
res+=(C-gas)*L[s][0]
gas=C-cost
return tryDrive(sec,gas,res)
else:
cost=(L[best][1]-L[s][1])/Dvg
res+=(cost-gas)*L[s][0]
gas=0
return tryDrive(best,gas,res)
res=tryDrive(0,0,0)
编辑于 2018-09-05 17:13:26
回复(0)
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
struct position
{
double price;
double distance;
position()=default;
position(double p,double dis):price(p),distance(dis) {}
};
bool cmp(position &p1,position &p2){
return p1.distance<p2.distance;
}
int main(){
int n;
double capacity,dis,use;
scanf("%lf%lf%lf%d",&capacity,&dis,&use,&n);
vector<position> data;
for(int i=0;i<n;i++){
double tmp1,tmp2;
scanf("%lf%lf",&tmp1,&tmp2);
data.push_back(position(tmp1,tmp2));
}
sort(data.begin(),data.end(),cmp);
if(data[0].distance>0) {
printf("The maximum travel distance = %.2lf",0.00);
return 0;
}
double sum=0,cap=0;
int i=0;
bool out=false;
double maxdis=0;
while(i<n){
maxdis=data[i].distance+use*capacity;
int j=i+1;
int minIndex=i+1;
while(j<n){
if(data[j].distance>maxdis) break;
if(data[j].price<data[i].price) break;
if(data[minIndex].price>data[j].price)
minIndex=j;
j++;
}
if(i==n-1){
if(maxdis>=dis){
sum+=((dis-data[i].distance)*1.0/use-cap)*data[i].price;
out=true;
break;
}
else{
break;
}
}
else if(j>=n){
if(maxdis>=dis){
double err=(dis-data[i].distance)*1.0/use;
sum+=(err-cap)*data[i].price;
out=true;
break;
}
else{
double err=(data[minIndex].distance-data[i].distance)*1.0/use;
sum+=(capacity-cap)*data[i].price;
cap=capacity-err;
i=minIndex;
}
}
else if(data[j].distance>maxdis&&j==i+1){
break;
}
else if(data[j].distance<=maxdis&&data[j].price<data[i].price){
double err=(data[j].distance-data[i].distance)*1.0/use;
sum+=(err-cap)*data[i].price;
cap=0;
i=j;
}
else{
double err=(data[minIndex].distance-data[i].distance)*1.0/use;
sum+=(capacity-cap)*data[i].price;
cap=capacity-err;
i=minIndex;
}
}
if(out==false)
printf("The maximum travel distance = %.2lf",maxdis);
else
printf("%.2lf",sum);
system("pause");
return 0;
}
发表于 2018-02-27 13:08:26
回复(0)
题意：计算从杭州到指定路程，需要花费的油费。由于在道路各个地方都有加油站，且它们的油价是不同的，所以就是一个选择加油站加油的问题了。
思路：贪心，关键是读懂题目的意思，将解题步骤先在纸上演算一遍，然后再将这些步骤转换成代码
贪心策略：
1.即找到满油最大行驶距离中，最近的低于当前油价的加油站
2.若没有，则找到其中价格最低的加油站
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const int maxn = 510;
const int INF = 1000000000;
struct station
{
double price, dis; //加油站的油价、距离
}st[maxn];
bool cmp(station a, station b) //结构体station的比较函数，按其距离的从小到大排序
{
return a.dis < b.dis;
}
int main()
{
freopen("C:\\Documents and Settings\\Administrator\\桌面\\data.txt", "r", stdin); // 我把这个and不小心写成了ans怪不得读入不了数据呀呀
double Cmax, D, Davg; //最大存油量、目的地的距离、每单位油量行驶路程
int N; //加油站总数
scanf("%lf%lf%lf%d", &Cmax, &D, &Davg, &N);
for (int i = 0; i < N; i++)
{
scanf("%lf%lf", &st[i].price, &st[i].dis);
}
st[N].dis = D; //将目的地设置为最后一个加油站
st[N].price = 0.0;
sort(st, st + N, cmp); //将加油站按距离从小到大排序
double maxDis = Cmax * Davg; //满油时，最大行驶距离
if (st[0].dis != 0) //第一个加油站不在起点处，没油，无法行驶
printf("The maximum travel distance = 0.00\n");
else
{
int now = 0; //当前的加油站编号
double ans = 0, nowTank = 0; //总费用、当前的油量
while (now < N) //未达目的地时，循环
{
int k = -1; //最低油价的加油站编号
double priceMin = INF; //最低价格
/*for循环里面是两个贪心策略，即找到满油最大行驶距离中，最近的低于当前油价的加油站
若没有，则找到其中价格最低的加油站*/
for (int i = now + 1; st[i].dis - st[now].dis <= maxDis && i <= N; i++)
{ //在满油下，最大行驶路程中寻找
if (priceMin > st[i].price) //找到最低油价
{
priceMin = st[i].price;
k = i; //标记下一个要加油的加油站为k
if (priceMin < st[now].price) //找到第一个小于当前油价，跳出循环
{
break;
}
}
}
if (k == -1) //在最大行驶路程中，已经没有加油站了，故只能停止
break;
double need = (st[k].dis - st[now].dis) / Davg; //到达下一个加油站的需油量，这个变量设置的很有用呀，的确要设置这样一个变量的
if (priceMin < st[now].price) //如果最低价格小于当前价格
{
if (nowTank < need) //油箱存油量小于需求值
{
ans += (need - nowTank) * st[now].price; //在现在的加油站加油，直到满足需要
nowTank = 0; //开到了下一个目标加油站，油箱已然没油了
}
else
{
nowTank -= need; //油箱存油量大于需求值，直接可用去需求量即可
}
}
else //即最低价格大于当前价格，找到在满油最大行驶距离中，价格最低的加油站
{
//因为当前加油站的价格小于，在满油最大行驶距离中，任何一个加油站的价格，所以需要在当前加油站加满油
ans += (Cmax - nowTank) * st[now].price;
nowTank = Cmax - need; //用掉需求量
}
now = k; //到达目的加油站k
}
if (now == N) //已经到达目的地N
{
printf("%.2f\n", ans); //打印出耗费
}
else
{
//不能到达目的地，输出最大行驶距离，即当前加油站距离出发地的距离加上满油的最大行驶距离
printf("The maximum travel distance = %.2f\n", st[now].dis + maxDis);
}
}
while (1);
return 0;
}
发表于 2017-09-05 09:35:49
回复(0)
这道题首先要注意几个坑，题目没有说明白：
1. 同一距离可能有多个加油站
2. 要用double型表示 Int和float都会有精度的问题
下面说一说我的思路：
1.把pair<double,double>用来表示每个加油站<distance,price>，然后按照distance的升序排列（记得保留同一距离的加油站中，价格最小的那个加油站）
2.用curdis标注当前距离，index表示当前的加油站号,gap表示加满油的最大行车距离；
如果当前加油站和下一站的距离大于gap，那么输出curdis+gap为最远的可达距离，return 0;
否则，转入3.
3.以当前站index向前gap的范围内，寻找油价最便宜的那个加油站：
if(当前的位置就是最便宜的加油站)：
那么则加满油，如果可以在加满油之前直接到达目的地，那么OK，目的达到，退出函数；否则，在向前gap的范围内寻找次最优的加油站作为“nextindex”，即下一站。
else:
在当前位置加油，保证油量刚好可以行驶到下一个比当前加油站便宜的加油站nextindex。
下面是我的代码实现：
/*
0 1998898814
2 51 799559525.6+51+50+19.2
3 64
7 50
12 8
20 60
*/
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<vector>
#include<string>
#include<string.h>
#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;
vector<pair<double,double> > station;
bool cmp( pair<double,double> p1, pair<double,double>p2 ){
if(p1.first == p2.first)
return p1.second < p2.second;
return p1.first < p2.first;
}
int main(){
double capacity, distance, per;
int nums;
cin>>capacity>>distance>>per>>nums;
for(int i = 0;i<nums;i++){
double d;
double price;
cin>>price>>d;
station.push_back(make_pair(d,price));
}
sort(station.begin(),station.end(),cmp);
vector<pair<double,double> > s;
int j = 0;
for(;j<station.size();){
int di = station[j].first;
s.push_back(station[j]);
while(di == station[j].first)
j++;
}
station = s;
double cost = 0;
double curdis = 0;
int index = 0;
double gap = per*capacity;
double leftgas = 0;
for( ; index<station.size() ;){
if(index == station.size()-1) break;
curdis = station[index].first;
if(index+1<station.size() && station[index+1].first-station[index].first <= gap){
int minindex = index;
double minprice = station[index].second;
int tmpindex = index+1;
while( tmpindex<station.size() && station[tmpindex].first-station[index].first<=gap){
if( station[tmpindex].second < station[minindex].second )
minindex = tmpindex;
tmpindex++;
}
if(minindex == index){ //假如当前为最优站 而且下一站可达,那么则加满油
if(distance-curdis > per*capacity )
cost += ( (capacity-leftgas)*station[minindex].second );
else{
cost += (distance-curdis)/per * station[minindex].second;
printf("%.2f",cost);
return 0;
}
int nextone = index+1;
int nextindex = index+1; //下一个最优惠的站 修改了一下！原来是tmpindex-1
int nextminprice = station[nextindex].second;
while( nextone < station.size() && station[nextone].first-station[index].first < gap ){
if( station[nextone].second < nextminprice){
nextminprice = station[nextone].second;
nextindex = nextone;
}
nextone++;
}
leftgas = (double)(capacity-( ( station[nextindex].first-station[index].first )/per ));
index = nextindex;
}
else{
int k = index+1; //假如gap范围内存在最优站，则加油至可以行驶到下一个更实惠的站
for( ; k<=minindex;k++){
if(station[k].second < station[index].second){
cost+=( (station[k].first-station[index].first-leftgas*per)/per * station[index].second );
break;
}
}
//cost += ( (station[minindex].first-station[index].first-leftgas*per)/per* station[index].second );
leftgas = 0;
index = k;
}
}
else{
double farest = curdis+gap;
cout<<"The maximum travel distance = ";
printf("%.2f",farest);
return 0;
}
}
if(index == station.size()-1){
if( distance-station[index].first > gap ){
double far = gap+station[index].first;
cout<<"The maximum travel distance = ";
printf("%.2f",far);
return 0;
}
else{
cost += ( (distance-station[index].first-leftgas*per)/per * station[index].second );
}
}
printf("%.2f",cost);
}
发表于 2017-07-31 15:53:52
回复(0)
//贪心算法，考虑每次到加油站都加满油，但是没次都用最便宜的油，然后到加油站把比当前油贵的所有油都换了，然后再加满，钱只算用的油。暂时想不到其他方法了，感觉有点乱。。
#include
<iostream>
#include <stdio.h>
#include <utility>
#include <deque>
#include <algorithm>
using namespace std ;
typedef struct station
{
double price;
int distance;
}Station;
int cmp( Station a, Station b)
{
return a. distance <b. distance ;
}
Station sta[500];
int main( int argc, const char * argv[]) {
int c,distance,davg,n;
scanf ( "%d %d %d %d" ,&c,&distance,&davg,&n);
int i;
for (i=0;i<n;i++)
scanf ( "%lf%d" ,& sta [i]. price ,& sta [i]. distance );
sort ( sta , sta +n, cmp ); // 输入完成
pair < double , double > P;
deque < pair < double , double > > D; // 油箱中的油
double newco=0.0,di=0.0,pri=0.0;
for (i=0;i<n;i++)
{
if (di+newco*davg< sta [i]. distance )
{
printf ( "The maximum travel distance = %.2lf\n" ,di+newco*davg);
return 0;
}
else
{
double k=( sta [i]. distance -di)*1.0/davg;
newco -= k;
while (k>0)
{
if (!D. empty ()&&k>=D. front (). first )
{
k = k-D. front (). first ;
pri = pri +D. front (). second *D. front (). first ;
D. pop_front ();
}
else
{
D. front (). first = D. front (). first - k;
pri = pri +k*D. front (). second ;
k=0;
}
}
if (newco==0)
{
P. first = c;
P. second = sta [i]. price ;
D. push_back (P);
}
else
{
while (!D. empty ()&& sta [i]. price <= D. back (). second )
{
newco -= D. back (). first ;
D. pop_back ();
}
P. first = (c-newco);
P. second = sta [i]. price ;
D. push_back (P);
}
}
di= sta [i]. distance ;
newco=c;
}
if (di+newco*davg<distance)
{
printf ( "The maximum travel distance = %.2lf\n" ,di+newco*davg);
return 0;
}
else
{
double k=(distance-di)*1.0/davg;
newco -= k;
while (k>0)
{
if (!D. empty ()&&k>=D. front (). first )
{
k = k-D. front (). first ;
pri = pri +D. front (). second *D. front (). first ;
D. pop_front ();
}
else
{
D. front (). first = D. front (). first - k;
pri = pri +k*D. front (). second ;
k=0;
}
}
}
printf ( "%.2lf" ,pri);
return 0;
}
发表于 2017-01-10 14:49:28
回复(0)
问题信息
难度：
21条回答
14收藏
7169浏览
通过挑战的用户
-
2023-03-12 19:02:56
-
2023-02-22 13:10:22 -
2023-02-21 00:13:09
-
2023-01-22 13:08:53
-
2022-11-27 00:45:36
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
