Building an Aquarium

题目连结

解题

应先具备以下能力

binary searchvertor知道从底部一层一层的看太慢了会LTE(MD我-2)

代名词

top 题目给并的最高处(可以用1e10或INT_MAX)bottom最低点初始值为1，也是这次的输出值mid二分搜寻法的关键，用其来测试是否会超过或少于可使用的水量x题目给的可使用最大水量use_water计算这层所需要的水量

解题关键:
一.用二分搜寻法找中心层
二.用中心层去计算使用的水量
三.如果用的水量大于允许的水量那就把新最高点移到中心点====>新的中心点就会是(新的最高点+最低点)/2+最低点

从上往下看，找到中心点mid(mid=bottom+(top-bottom)/2)，用mid计算要多少水(use_water)

if:use_water > x ==>把top=mid ==> 会在得到新的mid==>再去计算
if:use_water < x ==>把bottom=mid ==>会的到新的mid==>再去计算

如果这样还看不懂可以直接来问我，但请先至少知道二分搜寻法

code

#include <iostream>#include <vector>#define ll long longusing 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;}