b310 - 英靈召喚
題目描述
題目要求找出蒐集到所需魔力 m 的最短連續時間。給定 n 秒內大地釋放的魔力量 a[i]，需要找到一個連續的時間段，使得該時間段內蒐集到的魔力總和大於等於 m。如果 n 秒內無法蒐集到足夠的魔力，則輸出 "GGGGGZ"。
解題思路
本題可以使用二分搜尋法來解決。首先，計算所有魔力的總和，如果總和小於所需魔力 m，則直接輸出 "GGGGGZ"。否則，使用二分搜尋來尋找最短的連續時間。
二分搜尋的範圍是 [0, n]。對於每個中間值 t，使用一個迴圈來計算從 0 到 n-1 秒，長度為 2*t+1 的時間段內蒐集到的魔力總和。具體來說，迴圈中計算從 i 到 i+t 的魔力總和，並檢查是否大於等於 m。如果存在一個時間段滿足條件，則更新右邊界為 mid-1，否則更新左邊界為 mid+1。
使用 prefix sum 的概念可以優化計算時間段內魔力總和的過程。
複雜度分析
- 時間複雜度: O(n log n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
long long int a[1000001],m,n,total;
bool judge(int t){
long long int tmp=0;
for(int i=0,j=-t;i<n;++i,++j){
tmp+=a[i];
if(j>=0)tmp-=a[j];
if(tmp>=m)return 1;
}
return 0;
}
int bs(int l,int r){
if(r<l)return l;
int mid=(l+r)/2;
if(judge(mid))
return bs(l,mid-1);
else
return bs(mid+1,r);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=0;i<n;++i){
cin >> a[i];
total+=a[i];
}
if(total<m)
cout << "GGGGGZ";
else
cout << bs(0,n);
}