網(wǎng)站設(shè)計(jì)寬屏/品牌策略有哪些
題目
思路
--剛開始想到暴力嘗試的方法,但是N太大了,第一個(gè)測(cè)試點(diǎn)都超時(shí)。題目中說(shuō)前k個(gè)石頭的和還有后k個(gè)石頭的和要小于s,在這里要能想到開一個(gè)數(shù)組來(lái)求前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之后,并不能確定中心位置在哪里,或者說(shuō),這個(gè)2k長(zhǎng)度的序列在整個(gè)序列的哪個(gè)位置,這時(shí)還需要遍歷,可以單拎出來(lái)整一個(gè)判斷k是否滿足條件的函數(shù)。
--如果整個(gè)sum數(shù)組從0開始,在后續(xù)遍歷位置相減求前k個(gè)數(shù)的和時(shí),沒(méi)有辦法取得下標(biāo)為0的數(shù)的值,必須要減去sum[-1],所以就讓數(shù)組從1開始,可以解決這個(gè)問(wèn)題。
--二分查找我用的還不是很熟練,在做題時(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;} //如果沒(méi)有找到,就縮小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;
}