fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #define int long long
  5. using namespace std;
  6.  
  7. bool canCompleteRace(const vector<int>& fuel, const vector<int>& time, int fuelCapacity, int timeLimit) {
  8.     int n = fuel.size();
  9.  
  10.     long long currentFuel = fuelCapacity;
  11.     long long currentTime = 0;
  12.  
  13.     for (int i = 0; i < n; i++) {
  14.         // Kiểm tra xem xe có thể đi tiếp đến trạm xăng i+1 không
  15.         if (currentFuel < fuel[i])
  16.             return false;
  17.  
  18.         // Trừ đi lượng xăng đã tiêu hao để đi đến trạm xăng i+1
  19.         currentFuel -= fuel[i];
  20.  
  21.         // Đổ lại đủ xăng tại trạm xăng i+1 nếu cần
  22.         long long fuelNeeded = max(0LL, fuel[i+1] - currentFuel);
  23.         currentFuel += fuelNeeded;
  24.         currentTime += fuelNeeded * time[i];
  25.  
  26.         // Tính thời gian cần để đổ xăng tại trạm xăng i+1
  27.         currentTime += (fuel[i+1] - fuelNeeded) * time[i];
  28.     }
  29.  
  30.     return currentTime <= timeLimit;
  31. }
  32.  
  33. long long minRefuelingTime(const vector<int>& fuel, const vector<int>& time) {
  34.     int n = fuel.size();
  35.  
  36.     // Kiểm tra trường hợp đầu tiên: không có đủ xăng để đi từ trạm xăng 1 đến trạm xăng N
  37.     if (fuel[0] < fuel[n-1])
  38.         return -1;
  39.  
  40.     long long left = 0;
  41.     long long right = 1e18;
  42.     long long minTime = -1;
  43.  
  44.     while (left <= right) {
  45.         long long mid = left + (right - left) / 2;
  46.  
  47.         if (canCompleteRace(fuel, time, fuel[0], mid)) {
  48.             minTime = mid;
  49.             right = mid - 1;
  50.         } else {
  51.             left = mid + 1;
  52.         }
  53.     }
  54.  
  55.     return minTime;
  56. }
  57.  
  58. main() {
  59.     int N;
  60.     cin >> N;
  61.  
  62.     vector<int> fuel(N);
  63.     vector<int> time(N);
  64.  
  65.     for (int i = 0; i < N; i++) {
  66.         cin >> fuel[i];
  67.     }
  68.  
  69.     for (int i = 0; i < N; i++) {
  70.         cin >> time[i];
  71.     }
  72.  
  73.     long long result = minRefuelingTime(fuel, time);
  74.     cout << result << endl;
  75.  
  76.     return 0;
  77. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
3
3 3 3
3 2 1
stdout
copy 
48
https://ideone.com/ZflJX3
language:
C++14 (gcc 8.3)
created:
237 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!