發表新討論
#9354: 錯在哪??


a11004 (Moriarty)

學校 : 高雄巿瑞祥高級中學
編號 : 44147
來源 : [36.239.35.18]
最後登入時間 ：
2018-09-14 01:18:31
b310. 英靈召喚 -- 103學年度板橋高中校內資訊學科能力競賽（三） | From: [124.8.140.182] | 發表日期 : 2014-10-26 20:52
#include<iostream>
using namespace std;
int main()
{
long long int N=0,M=0;
while(cin>>N>>M)
{
long long int A[N],a=0,j,i,c,B[N],tem,d=0,m,k,l;
for(i=0;i<N;i++)
{
        cin>>A[i];
        a=a+A[i];
}
if(a<M)
cout<<"GGGGGZ"<<endl;
else
{
    for(i=0;i<N-1;i++)
    {
                      if(A[i]>=M)
                      {
                                 if(M==0)
                                 cout<<"0"<<endl;
                                 else
                                 cout<<"1"<<endl;
                                 goto END;
                      }
                      else
                      {
                          m=A[i];
                          for(j=i+1;j<N;j++)
                          {
                                            m=m+A[j];
                                            if(m>=M)
                                            {
                                                    B[d]=j-i+1;
                                                    d=d+1;
                                                    break;
                                            }
                          }
                      }
    }
    for(k=0;k<d-1;k++)
    {
                      for(l=k+1;l<d;l++)
                      {
                                        if(B[k]>B[l])
                                        {
                                                     tem=B[k];
                                                     B[k]=B[l];
                                                     B[l]=tem;
                                        }
                      }
    }
    cout<<""<<B[0]<<""<<endl;
}
END:;
}
   return 0;
}
 
#9358: Re:錯在哪??


gtyuse (gtyuse)

學校 : 國立科學工業園區實驗高級中學
編號 : 37104
來源 : [140.112.215.56]
最後登入時間 ：
2021-02-18 08:23:14
b310. 英靈召喚 -- 103學年度板橋高中校內資訊學科能力競賽（三） | From: [123.110.232.18] | 發表日期 : 2014-10-27 19:56
應該是 TLE 吧
雖然跑得出答案, 但時間複雜度不對
如果不了解時間複雜度和 Big O notation 的話可以 Google
 
1. 注意你的程式碼中兩個雙層迴圈
( 一個好像是找可行的最小區間, 另一個是泡沫排序 ) 
時間複雜度都是 O(n^2), 這題 n 可到 10^6 也就是 100W
n^2 顯然超過時間
 
2. 這題要找的是區間和, 並且無更新動作
即為最簡單的 Prefix sum ( 前綴和 )
=> 可以先建一個陣列 sum[], 其中 sum[i]=array[i]+sum[i-1];
如此可以 sum[a]-sum[b-1] , O(1) 查詢區間 [a,b] 的和
 
3. 因為求最小的且數字皆為正
=> 可能有一決定性的位置滿足題目要求
故可利用 Binary Search ( 二分搜 ) 
二分搜複雜度為 O(log n) 
窮舉所有起點為 O(n) (可以加 cut, 不過不加也還好)
這樣整個問題便是 O(n log n)
多練習就能理解的, 加油嘿 
 


 
ZeroJudge Forum