發表新討論
#27953: 請問哪裡錯了


910580@mail.pcsh.ntpc.edu.tw (29劉佳翰)

學校 : 新北市立板橋高級中學
編號 : 163586
來源 : [114.24.177.219]
最後登入時間 ：
2022-01-08 17:16:18
g277. 3. 幸運數字 -- 2021年9月APCS | From: [114.24.231.31] | 發表日期 : 2021-11-06 21:44

我在測試執行時都正確，而測驗結果在#0~#17是WA，在#18是TLE

我知道VLA是非標準寫法，但是也不應該會錯啊

int main(){
    int n,small=10000000,m,sum_l=0,sum_r=0;
    cin >>n;
    int a[n],l=0,r=n-1;
    for(int i=0;i<n;i++)
        cin>>a[i];
    do{
    small=10000000;
    for(int i=l;i<=r;i++){
        if(a[i]<small){
            small=a[i];
            m=i;
        }
    }
    for(int i=l;i<m;i++){
        sum_l +=a[i];
    }
    for(int i=m+1;i<=r;i++){
        sum_r +=a[i];
    }
    if(sum_l>sum_r){
        l=l;
        r=m-1;
        sum_l=0;
        sum_r=0;
    }
    else if(sum_r>=sum_l){
        l=m+1;
        r=r;
        sum_l=0;
        sum_r=0;
    }
    }while(r-l>1);
    if(r==l){
        cout <<a[l];
    }
    else if (a[l]>a[r]){
        cout<< a[l];
    }
    else if (a[r]>a[l]){
        cout<< a[r];
    }
    return 0;
}
 
#27954: Re:請問哪裡錯了


LittleOrange666 (LittleOrange666)

學校 : 國立科學工業園區實驗高級中學
編號 : 173827
來源 : [140.126.248.232]
最後登入時間 ：
2023-06-07 14:09:36
g277. 3. 幸運數字 -- 2021年9月APCS | From: [180.177.3.37] | 發表日期 : 2021-11-06 22:50

我在測試執行時都正確，而測驗結果在#0~#17是WA，在#18是TLE

我知道VLA是非標準寫法，但是也不應該會錯啊

int main(){
    int n,small=10000000,m,sum_l=0,sum_r=0;
    cin >>n;
    int a[n],l=0,r=n-1;
    for(int i=0;i<n;i++)
        cin>>a[i];
    do{
    small=10000000;
    for(int i=l;i<=r;i++){
        if(a[i]<small){
            small=a[i];
            m=i;
        }
    }
    for(int i=l;i<m;i++){
        sum_l +=a[i];
    }
    for(int i=m+1;i<=r;i++){
        sum_r +=a[i];
    }
    if(sum_l>sum_r){
        l=l;
        r=m-1;
        sum_l=0;
        sum_r=0;
    }
    else if(sum_r>=sum_l){
        l=m+1;
        r=r;
        sum_l=0;
        sum_r=0;
    }
    }while(r-l>1);
    if(r==l){
        cout <<a[l];
    }
    else if (a[l]>a[r]){
        cout<< a[l];
    }
    else if (a[r]>a[l]){
        cout<< a[r];
    }
    return 0;
}


sum要用long long，不然會溢位

 
#27962: Re:請問哪裡錯了


910580@mail.pcsh.ntpc.edu.tw (29劉佳翰)

學校 : 新北市立板橋高級中學
編號 : 163586
來源 : [114.24.177.219]
最後登入時間 ：
2022-01-08 17:16:18
g277. 3. 幸運數字 -- 2021年9月APCS | From: [114.24.231.31] | 發表日期 : 2021-11-07 08:31

改成long int 後解決了#0~#17的WA，

可是在#18依然TLE。

我猜#18可能是針對這種算法的測資（類似遞增或遞減，每次去除大於m+1或小於m-1的數量少，所以迴圈就要跑很多次）

也可能單純是數字很大，有沒有甚麼加速的方法呢?

或其實我的程式在特殊條件下會進入無窮迴圈?

 
ZeroJudge Forum