題目

思路

--剛開始想到暴力嘗試的方法，但是N太大了，第一個測試點都超時。題目中說前k個石頭的和還有后k個石頭的和要小于s，在這里要能想到開一個數(shù)組來求前n個石頭的總重，然后求前k個的直接將sum[i]-sum[i-k-1]就行了，這樣就不用再加個循環(huán)求和了，直接相減，降低了時間復(fù)雜度。題目中是讓求k的，而這個k可以取值的條件與k在數(shù)組中的位置有關(guān)?？梢詮?到n/2范圍遍歷，當(dāng)然時間復(fù)雜度比較大，換用二分查找。二分查找可以遍歷每一種可能的k值，并且時間復(fù)雜度較小。因為我們在假定一個k之后，并不能確定中心位置在哪里，或者說，這個2k長度的序列在整個序列的哪個位置，這時還需要遍歷，可以單拎出來整一個判斷k是否滿足條件的函數(shù)。

--如果整個sum數(shù)組從0開始，在后續(xù)遍歷位置相減求前k個數(shù)的和時，沒有辦法取得下標(biāo)為0的數(shù)的值，必須要減去sum[-1]，所以就讓數(shù)組從1開始，可以解決這個問題。

--二分查找我用的還不是很熟練，在做題時要弄兩個例子，一個是奇數(shù)長度的，一個是偶數(shù)長度的，試一試，確保循環(huán)不會卡死還有mid取值合理。

代碼

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;long long n, s;
long long sum[1000001]; //表示當(dāng)前所有石頭的重量和。
int k = 0; bool chazhao(int mid){for (long long i = mid; i + mid <= n; i++){if (sum[i] - sum[i - mid] <= s && sum[i + mid] - sum[i] <= s){return true;}}return false;
} //尋找符合條件的mid，這里的mid = k，也就是在尋找合適的k。因為并不確定n的奇偶性。 void zheban(int low, int high) {while (low <= high) {int mid = (low + high) / 2;if (chazhao(mid)){k = mid; low = mid + 1;} //如果找到，就逐步擴(kuò)大mid，即擴(kuò)大k。 else{high = mid - 1;} //如果沒有找到，就縮小k。 }
}int main(){cin >> n >> s; sum[0] = 0;for (int i = 1; i <= n; i++){int w;cin >> w;sum[i] = w + sum[i - 1];}zheban(1, n); //折半查找k。 cout << k * 2 << endl;return 0;
}