题目

https://www.matiji.net/exam/brushquestion/3/4347/179CE77A7B772D15A8C00DD8198AAC74?from=1

题目大意：给定n个科学家每秒获得理解力的大小和开始理解的时间，给定理解第五维度需要的总理解力。同时，可以随机让一位科学家在某一时刻消失，其理解力清0，并之后不会再产生理解力。求在尽可能晚的情况下，人类理解第五维度的最早时间点（最晚最早问题）。

分析

看了很多题解，都给了这么一句话：一般看到最（大/小）的最（小/大），都是用二分求解。所以这里可以对人类理解第五维度的时间点进行二分，由于求的是最早时间点，所以应该用if check(mid) r = mid; else l = mid + 1;的模板（二分模板参考：https://blog.csdn.net/destiny_balabala/article/details/104892394）。

对于check()函数，作用是判断二分的答案是否能满足所有科学家的累计贡献度超过m。由于要求尽可能晚的让人类理解第五维度，所以在计算累计贡献度的时候，需要排除掉贡献度最大的科学家（贪心的思想）。

时间复杂度方面，二分最小值是1，最大值是m（数据范围中，理解力大的最大值）每次check函数求累计贡献度需要执行n次（数据范围中，科学家的数量），所以复杂度为 $O(nlog_2m)$ 。题目中，m最大为 $2*10^9$ ，n最大为 $10^5$ 。所以 $log_2m = log_22*10^9 < log_22*16^9<log_22*2^{36}=37$ ， $nlog_2m<n*37=3.7*10^6$ ，所以不会超时。

代码

#include<bits/stdc++.h> using namespace std;typedef long long ll;const int N = 100010;
int n, m;
int s[N], v[N];int check(ll t) {// 如果能让人类理解第五维度，则返回1；否则返回0 ll sum = 0, _max = -1;for(int i = 0; i < n; i ++ ) {ll cur = max((t - s[i]) * v[i], 0ll); // s * v最大可能为10^12，所以这里要用long long_max = max(_max, cur);sum += cur;} return sum - _max > m;
}int main( )
{scanf("%d%d", &n ,&m);for(int i = 0; i < n; i ++ ) scanf("%d%d", &s[i], &v[i]);ll l = 1, r = 2e9;ll ans = -1;while (l < r) {int mid = l + r >> 1;if (check(mid)) { r = mid;ans = mid;}else l = mid + 1;}cout << ans << endl;return 0;
}