從最小的可能解，到最大的可能解之間偷俭，通過(guò)二分查找浪讳，驗(yàn)證每一個(gè)mid是否為解。
二分的過(guò)程是這樣的：
定義變量ans涌萤，儲(chǔ)存當(dāng)前優(yōu)解淹遵。定義閉區(qū)間[left, right]，代表程序當(dāng)前正在此閉區(qū)間內(nèi)尋找答案（尋找潛在的比ans更優(yōu)的解）负溪。
令mid = (left + right)/2
若mid為解透揣，則ans = max(ans, mid), left = mid + 1. 此時(shí)我們更新了最優(yōu)解，同時(shí)在最優(yōu)解的右側(cè)尋找潛在的更優(yōu)解笙以。
若mid不為解淌实，則right = mid - 1. mid不是解，因此我們?cè)趍id左邊尋找更優(yōu)解猖腕。
重復(fù)上述過(guò)程拆祈，直到left > right時(shí)跳出循環(huán)，ans即為最優(yōu)解倘感。
#include <iostream>
using namespace std;
int l[10001], s[10001], n, m;
bool check(int x) {
int total = 0;
for (int i = 1; i <= n; i++) {
total += (l[i]/x)*s[i];
}
return total >= m;
}
int main() {
cin >> n >> m >> l[1] >> s[1];
for (int i = 2; i <= n; i++) {
l[i] = (l[i-1]*37011+10193)%10000+1;
s[i] = (s[i-1]*73011+24793)%100+1;
}
int low = 1, high = 10000, ans = 0;
while (low <= high) {
int mid = low + (high-low)/2;
if (check(mid)) {
low = mid + 1;
ans = max(ans, mid);
} else {
high = mid - 1;
}
}
cout << ans << endl;
return 0;
}
