算法
1
4,2,9,11,
4,
2,4
2,4,9
42
4
2
4 9
2（0）
4（1） 9（2）
11（3）
11（0）
11（1） 9（2）
11（3）
2
https://leetcode.cn/problems/minimum-time-to-complete-trips/
class Solution {
public:long long minimumTime(vector<int>& time, int totalTrips) {long long minTime = time[0];for (int i : time) {if (i < minTime){minTime = i;}}long long leftB = (minTime - 1)?(minTime - 1):1;long long rightB = minTime * totalTrips;long long mid;cout<<"leftB"<<leftB<<" rightB"<<rightB<<" expectMid"<<(leftB+rightB)/2<<endl;while (leftB <= rightB) {mid = (leftB + rightB) / 2;if(leftB==rightB)break;long long sum = 0;for (int i : time) {sum += (mid / i);}if (sum < totalTrips) {//cout <<"左侧为"<<leftB<<"右侧为"<<rightB<<"此时时间是"<<mid<< " 此时的出行次数是" << sum << endl;leftB = mid + 1;}else {//cout<<"左侧为"<<leftB<<"右侧为"<<rightB<<"此时时间是"<<mid<< " 此时的出行次数是" << sum << endl;rightB = mid;}}return mid;}
};
第一次是因为没有考虑到可能有多个情况满足条件，即解集有多个，但存在最优解，如果写成单点搜索的话，则很可能找不到最优解；
于是改为在匹配的情况中去尝试缩减答案
第二次是因为没有考虑结果在域内的增长可能并不是线性的，即不是1个1个的增，值域并不遍布全体，比如要搜索的区间是1-100，但是可取值，可取到的区间可能只是其中的一个子集，由于问题的特殊性而使的不规则增长导致
就是说搜索空间是A，由所搜索的数据所产生的结果所处的空间为B，要求是在A中找解使结果为R，有可能R就根本不在空间B当中，那么此时要找的应该是最接近B右侧的数据，这也就直接排除了单点搜索的可行性，因为可能根本就不存在
综合上面两点，二分搜索，就是去搜索满足条件的最左侧的值，也就是说，
- 如果满足条件了（包含大于和等于），也不退出搜索，而是保留right=mid(=mid就是在解集中保留了其中的一个可行解）
-
- 这样的话，若左侧还存在更好的解，由于right=mid,也会使搜索空间进一步缩小，以尝试取到那个解
-
- 而如果右侧没有更好的解，此时的mid就是的话，由于是让right=mid，在下一轮搜索中并没有剔除掉这个解，而左侧(mid)又没有更好的解，那么必然会使left不断mid+1，最终收束到这个right上
-
- 如果不满足条件，即小于时，则必定要把该点排出搜索空间，即left=mid+1
那么最后退出搜索的条件就是空间中只剩一个解，即left==right，此时就应当退出搜索
思考：退出搜索时所保留的mid，是否可能依然不满足条件？
解：当然有可能；但这取决于搜索空间本身的性质，若搜索空间中存在解，且满足单调性，那么最后的Mid必然满足条件；否则，若空间中就没有解，那么最后的mid也必然是搜索空间中某一端的值
最后一次，是因为sum开成了int,但存在比int大的数据，改为Longlong后通过
