一，思路：
1，做這題如果對二分敏感的話，看完題目就大概很容易想到，通過二分來找到一個 r ,使得 [ l, r] 之間的和最接近 u (因為這樣才是 Isaac 所能獲得的最大提升)。
2，還有一個特殊情況，結合代碼來說明。
二，代碼
#include <iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 1e5+10;
typedef long long ll;int arr[N];
ll pre[N];//u--->題目輸入的目標值
//st---> 題目輸入的起始坐標int u,st;//重寫二分比較函數
bool check(int mid) {if (pre[mid] - pre[st - 1] <= u) return true;return false;
}void sovle() {int n;cin >> n;for (int i = 0; i <= n; i++) pre[i] = 0;for (int i = 1; i <= n; i++) {cin >> arr[i];pre[i] = pre[i - 1] + arr[i];}int q;cin >> q;while (q--) {cin >> st >> u;int l=st,r = n;//二分模板while (l < r) {int mid = l + r + 1>> 1;if (check(mid)) l = mid;else r = mid - 1;}//特殊情況：
// 1.首先要知道，我們求得的 r只是 [l,r]之和小于等于u的那個位置，不一定是最接近的那個點。
// 2.舉個例子：
// （1）例如 數組：[1 ,2 ,8] ,目標值u = 10 , 起始位置 l = 1。（2）這里我們二分求得的是 r =2（1 + 2 = 3 < 10）,但是明顯 r=3 時更接近 u// 3.還有個陷阱，就是當他們的差距相等時，是選 r +1 還是 r 呢？如果不仔細分析的話，很容易
// 就會想當然認為是 r,因為 r < r +1.實則不是，這里我就不舉例了，你們自己可以將下面的判斷
// 改成 u - (pre[r] - pre[st - 1]) <= (pre[r + 1] - pre[st - 1]) - u 試一下，看是什么
// 結果，然后再去找出問題即可。//判斷離目標值最近的點是 r 還是 r +1if (r == n || u - (pre[r] - pre[st - 1]) < (pre[r + 1] - pre[st - 1]) - u) {cout << r <<" ";}else cout << r + 1 << " ";}cout << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--) {sovle();}return 0;
}
)
