題目

思路

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

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

--二分查找我用的還不是很熟練，在做題時(shí)要弄兩個(gè)例子，一個(gè)是奇數(shù)長(zhǎng)度的，一個(gè)是偶數(shù)長(zhǎng)度的，試一試，確保循環(huán)不會(huì)卡死還有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。因?yàn)椴⒉淮_定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;
}