Building an Aquarium

題目連結

解題

應先具備以下能力

• binary search
• vertor
• 知道從底部一層一層的看太慢了會LTE(MD我-2)

代名詞

• top 題目給並的最高處(可以用1e10或INT_MAX)
• bottom最低點初始值為1，也是這次的輸出值
• mid二分搜尋法的關鍵，用其來測試是否會超過或少於可使用的水量
• x題目給的可使用最大水量
• use_water計算這層所需要的水量

解題關鍵:
一.用二分搜尋法找中心層
二.用中心層去計算使用的水量
三.如果用的水量大於允許的水量那就把新最高點移到中心點====>新的中心點就會是(新的最高點+最低點)/2+最低點

1. 從上往下看，找到中心點mid(mid=bottom+(top-bottom)/2)，用mid計算要多少水(use_water)

2. if:use_water > x ==>把top=mid ==> 會在得到新的mid==>再去計算
   if:use_water < x ==>把bottom=mid ==>會的到新的mid==>再去計算

如果這樣還看不懂可以直接來問我，但請先至少知道二分搜尋法

code

#include <iostream>
#include <vector>

#define ll long long

using namespace std;

int main()
{

   int t;
   cin >> t;

   while (t--)
   {
       ll n, x, bottom = 1, top = 0;

       cin >> n >> x;
       vector<int> v(n);
       for (ll i = 0; i < n; i++)
       {
           cin >> v[i];
       }

       // binary search
       top = INT_MAX;
       while (bottom < top - 1)
       {
           ll mid = bottom + (top - bottom) / 2;
           ll use_water = 0;
           for (int i = 0; i < n; i++)
           {
               if (mid > v[i])
               {
                   use_water += (mid - v[i]);
               }
           }
           if (use_water > x)
           {
               top = mid;
           }
           else
           {
               bottom = mid;
           }
       }

       cout << bottom << endl;
   }
   return 0;
}