贪心求调,码风好
查看原帖
贪心求调,码风好
746944
PaluAix楼主2023/10/25 16:16
#include <bits/stdc++.h>
using namespace std;

double Dis, Cap, Tra, Pri;
double Cost;
int N, Now;

struct node {
  double dis, cost;
} a[10];

bool cmp(node a, node b) {
  return a.dis < b.dis;
}

int main() {
  cin >> Dis >> Cap >> Tra >> Pri >> N;
  for (int i = 1; i <= N; i++)
    cin >> a[i].dis >> a[i].cost;

  sort(a + 1, a + 1 + N, cmp);
  a[0].cost = Pri, a[0].dis = 0;
  if (!N && Cap * Tra < Dis) {
    cout << "No Solution" << endl;
    system("pause");
    return 0;
  }
  // 没油站而且出发时充满也跑不到
  double MaxDis = Cap * Tra;
  int Aim = Now;
  while (true) {
    // Now指向在可行驶距离内价格最小的油站
    bool flag = 0;
    for (int i = Now; i <= N; i++) {
      if (a[i].cost <= a[Aim].cost && a[i].dis - a[Now].dis <= MaxDis) {
        Cost += (a[i].dis - a[Now].dis) * a[Now].cost;
        Aim = i;
        flag = 1;
      }
    }
    Now = Aim;  // 更新一下
    if (!flag) {
      if (a[Now].dis + MaxDis >= Dis) {
        Cost += ((Dis - a[Now].dis) / Tra) * a[Now].cost;
        cout << Cost << endl;
        system("pause");
        return 0;
      }  // 可以跑出去
      else {
        cout << "No Solution" << endl;
        system("pause");
        return 0;
      }
    }
  }
}

2023/10/25 16:16
加载中...