1033 To Fill or Not to Fill 25 ★★★★

文章访问量:

很难受了，把问题想复杂了，又写了150行，而且还没debug出来，只能换了种方法。
github地址：https://github.com/iofu728/PAT-A-by-iofu728
难度：★★★★
关键词：贪心，模拟。

题目

1033.To Fill or Not to Fill (25)
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.

Input Specification:

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.

Output Specification:

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.

Sample Input 1:
50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300

Sample Output 1:
749.17

Sample Input 2:
50 1300 12 2
7.10 0
7.00 600

Sample Output 2:
The maximum travel distance = 1200.00

大意

公路上有n个加油站，每个加油站价格不一样，求设计最优加油方案，使得能到达目的地。如果不能达到目的地，请输出最远行驶距离。

思路

  1. 这题是贪心的题，我一开始想成线段合并的题目，一个个加油站看成线段的两端，线段长度最长600，求0点出发的最大线段长度。通过线段合并，来实现最远距离的求解。
  2. 如果可以到达目的地，则通过价格降序依次选择加油站。如果被选择到的加油站，被现有线段包含（注意是包含，就是完全在现有线段之中）那么舍去改线段。
  3. 如果margin之后的线段能到达目的地，则不再增加加油站。（注意补0点）
  4. 确定好加油站之后，每个加油站加多少油，则是一个很大的问题。
    一种考虑，如果在能行驶的距离（Cmax×Davg）中有价格更低的，则把油加到能行驶到下一个加油站。
    如果没有，则加满。

code

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int ability, d;
struct node {
  int start, end;
  double price;
};
struct oil {
  int dis;
  double price;
};
vector<node> v, m;
vector<oil> o;
bool cmpoilstart(oil a, oil b) {
  return (a.dis == b.dis) ? (a.price < b.price) : (a.dis < b.dis);
}
bool cmpoil(oil a, oil b) {
  return (a.price == b.price) ? (a.dis < b.dis) : (a.price < b.price);
}
bool cmpdis(node a, node b) { return a.start <= b.start; }
bool canreach() {
  sort(v.begin(), v.end(), cmpdis);
  for (int i = 1; i < v.size(); ++i) {
    if (v[i].start > v[i - 1].end) {
      return false;
    }
  }
  int endv = v.size() - 1;
  if (v[endv].end >= d) {
    return true;
  } else {
    return false;
  }
}
void margin(node temp) {
  int flag = 0;
  for (int i = 0; i < m.size(); ++i) {
    if (m[i].start <= temp.start && m[i].end >= temp.start) {
      m[i].end = temp.end;
      ++flag;
    } else if (m[i].start <= temp.end && m[i].end >= temp.end) {
      if (flag) {
        m[i].start = m[i - 1].start;
        m.erase(m.begin() + i - 1);
      } else {
        m[i].start = temp.start;
      }
      ++flag;
    }
  }
  if (!flag) m.push_back(temp);
}
bool lowprice(node temp) {
  for (int i = 1; i < v.size(); ++i) {
    if (v[i - 1].start < temp.start && v[i].start > temp.start &&
        v[i - 1].price > temp.price) {
      return true;
    }
  }
  return false;
}
bool havein(node temp) {
  for (int i = 0; i < m.size(); ++i) {
    if (m[i].start <= temp.start && m[i].end >= temp.end) {
      return false;
    }
  }
  return true;
}
int main(int argc, char const *argv[]) {
  int c, davg, n, p = 0;
  cin >> c >> d >> davg >> n;
  ability = c * davg;
  getchar();
  for (int i = 0; i < n; ++i) {
    oil temp;
    scanf("%lf %d", &temp.price, &temp.dis);
    o.push_back(temp);
  }
  sort(o.begin(), o.end(), cmpoilstart);
  if (o[0].dis) {
    cout << "The maximum travel distance = 0\n";
    return 0;
  }
  node first;
  first.start = 0, first.end = ability, first.price = o[0].price;
  v.push_back(first);
  m.push_back(first);
  int i = 0;
  while (!o[i].dis) {
    o.erase(o.begin() + i);
  }
  sort(o.begin(), o.end(), cmpoil);
  while (p != o.size() && !canreach()) {
    node temp;
    temp.start = o[p].dis;
    temp.price = o[p].price;
    int tempend = temp.start + ability;
    temp.end = (tempend > d) ? (d) : tempend;
    ++p;
    //      cout<<temp.start<<" "<<temp.end<<" "<<temp.price<<"
    //"<<canreach()<<"
    //"<<p<<" "<<v.size()<<" "<<m.size()<<endl;
    if (havein(temp)) {
      v.push_back(temp);
      margin(temp);
      //        for(int i=0;i<m.size();++i){
      //            cout<<'m'<<m[i].start<<" "<<m[i].end<<endl;
      //        }
      //        for(int i=0;i<v.size();++i){
      //            cout<<'v'<<v[i].start<<" "<<v[i].end<<"
      //"<<v[i].price<<endl;
      //        }
    } else if (lowprice(temp)) {
      v.push_back(temp);
    }
  }

  if (p == o.size() && !canreach()) {
    cout << "The maximum travel distance = " << m[0].end << endl;
  } else {
    int more = 0, tempstart;
    double spend = 0.0;
    sort(v.begin(), v.end(), cmpdis);
    for (int i = 1; i < v.size(); ++i) {
      tempstart = v[i].start - v[i - 1].start;
      if (v[i].price <= v[i - 1].price) {
        if (more < tempstart) {
          spend += (tempstart - more) * v[i - 1].price * 1.0;
          more = 0;
        } else {
          more -= tempstart;
        }

      } else {
        if (more >= 600) {
          more -= 600;
        } else {
          spend += (600 - more) * v[i - 1].price * 1.0;
          more = 600 - tempstart;
        }
      }
      // cout<<v[i].start<<" "<<v[i-1].start<<"
      //"<<spend<<endl;
    }

    spend += (d - v[v.size() - 1].start - more) * 1.0 * v[v.size() - 1].price;
    printf("%.2f\n", spend / davg);
  }

  return 0;
}
PATcpp
Prev
1034 Head of a Gang 30 ☆☆☆
Next
1026 Table Tennis (30)★★★★☆
累计访问量: | 昨日访问量: | 昨日爬虫数:
Gunjianpan © 2017 - 2020 Power by VuePress & iofu728/blog