b310(Q) - Error
題目描述
題目要求找出一個數列中，滿足子數列和至少為 b 的最短長度。如果找不到任何子數列滿足條件，則輸出 "GGGGGZ"。
解題思路
首先，計算數列的前綴和，以便快速計算任意子數列的和。然後，使用兩層迴圈遍歷所有可能的子數列，計算每個子數列的和，並檢查是否大於等於 b。如果找到滿足條件的子數列，則更新最短長度。如果遍歷完所有子數列後仍然沒有找到滿足條件的子數列，則輸出 "GGGGGZ"。如果前綴和的第一個元素就大於等於 b，則輸出 1。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(n)
程式碼
#include <stdio.h>
int main(){
long long int a,b;
while(scanf("%lld%lld",&a,&b)>0){
long long int sum[a];
for(int i=0;i<a;++i){
scanf("%lld",&sum[i]);
(i)?sum[i]+=sum[i-1]:1;
}
if(sum[a-1]<b)
printf("GGGGGZ\n");
else{
long long int ans=a+1;
if(sum[0]>=b)
printf("1\n");
else{
for(int i=0,z=1;i<a;++i,z=1){
for(int j=i+1;j<a;++j,++z){
if(sum[j]-sum[i]>=b){
if(z<ans)
ans=z;
break;
}
}
}
printf("%lld\n",ans);
}
}
}
}