fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. // Hàm kiểm tra tính khả thi và tính toán cost còn lại
  7. pair<bool, long long> isPossible(const vector<long long>& heights, int n, long long T, long long targetHeight) {
  8.     long long cost = 0; // Chi phí tổng
  9.     vector<long long> newHeights(heights); // Chiều cao sau khi giảm
  10.  
  11.     for (int i = 0; i < n; i++) {
  12.         if (newHeights[i] > targetHeight) {
  13.             cost += newHeights[i] - targetHeight;
  14.             newHeights[i] = targetHeight;
  15.         }
  16.     }
  17.  
  18.     for (int i = 1; i < n; i++) {
  19.         if (abs(newHeights[i] - newHeights[i - 1]) > 1) {
  20.             return {false, T}; // Không khả thi, trả về T
  21.         }
  22.     }
  23.  
  24.     return {cost <= T, T - cost}; // Trả về cost còn lại nếu khả thi
  25. }
  26.  
  27. int main() {
  28.     int n;
  29.     long long T;
  30.     cin >> n >> T;
  31.     vector<long long> heights(n);
  32.  
  33.     for (int i = 0; i < n; i++) {
  34.         cin >> heights[i];
  35.     }
  36.  
  37.     long long low = -1e15, high = 1e15;
  38.     long long result = -1e15;
  39.     long long remainingCost = 0;
  40.  
  41.     // Tìm kiếm nhị phân
  42.     while (low < high) {
  43.         long long mid = low + (high - low) / 2;
  44.         auto [possible, costLeft] = isPossible(heights, n, T, mid);
  45.         if (possible) {
  46.             // result = mid;
  47.             remainingCost = costLeft; // Lưu lại cost còn dư
  48.             high = mid;
  49.         } else {
  50.             low = mid + 1;            // Cố gắng tìm chiều cao thấp hơn
  51.         }
  52.         // cout << "mid: " << mid << " possible: " << possible << " costLeft: " << costLeft << endl;
  53.     }
  54.  
  55.     result = low;
  56.  
  57.     // Xử lý các case bổ sung
  58.     if (remainingCost >= 3 && n >= 2) {
  59.         // Giảm ô đầu thêm 2, ô thứ hai thêm 1
  60.         result = result - 2;
  61.     } else if (remainingCost > 0 && n >= 1) {
  62.         // Giảm ô đầu thêm 1
  63.         result = result - 1;
  64.     }
  65.  
  66.     // cout << "Chiều cao tối thiểu: " << result << endl;
  67.     // cout << "Cost còn lại: " << remainingCost << endl;
  68.  
  69.     cout << result << endl;
  70.  
  71.     return 0;
  72. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
4 3
1 1 1 1
stdout
copy 
-1
https://ideone.com/RqIVDE
language:
C++14 (gcc 8.3)
created:
4 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!