#31992: NA(score:35%)


0301alex (alex)

學校 : 不指定學校
編號 : 94037
來源 : [61.64.1.159]
最後登入時間 :
2024-04-09 19:58:33
h028. 202001_3 砍樹 -- 2020年1月APCS | From: [42.70.161.101] | 發表日期 : 2022-09-04 18:09

#include <iostream>
#include <vector>
using namespace std ;
int main () {
 vector<int> a , b ;
    int N , L ;
    while( cin >> N >> L ) {
        int x ;
        for( int i = 0 ; i < N ; i++ ) {
            cin >> x ;
            a.push_back(x) ;
        }
        for( int i = 0 ; i < N ; i++ ) {
            cin >> x ;
            b.push_back(x) ;
        }
        int min = 0 , max = L ;
        bool flag = true ;
        int cut = 0 ;
        int maxx = -2000 ;
        while( flag ) {
            flag = false ;
            for( int i = 0 ; i < a.size() ; ) {
                ( i != 0 ) ? min = a[i-1] : min = 0 ;
                ( i == N - 1 ) ? max = L : max = a[i+1] ;  
                if( a[i] - b[i] >= min || a[i] + b[i] <= max ) {
                    if( b[i] > maxx ) maxx = b[i] ;
                    a.erase( a.begin() + i ) ;
                    b.erase( b.begin() + i ) ;
                    cut++ ;
                    flag = true ;
                } else i++ ;
            }
        }
        cout << cut << endl << maxx << endl ;
    }
}

 
#32034: Re: NA(score:35%)


cges30901 (cges30901)

學校 : 不指定學校
編號 : 30877
來源 : [39.9.74.255]
最後登入時間 :
2024-10-14 22:20:08
h028. 202001_3 砍樹 -- 2020年1月APCS | From: [27.246.162.137] | 發表日期 : 2022-09-09 14:18

1.
                    a.erase( a.begin() + i ) ;
                    b.erase( b.begin() + i ) ;


1. 移除一棵樹之後N也要減1,不然前面i == N - 1判斷會出問題

2. 接下來只有60% TLE,你這種方法太慢了,可以嘗試改成單層的for迴圈,然後vector::erase速度不快也要改

 
#32590: Re: NA(score:35%)


0301alex (alex)

學校 : 不指定學校
編號 : 94037
來源 : [61.64.1.159]
最後登入時間 :
2024-04-09 19:58:33
h028. 202001_3 砍樹 -- 2020年1月APCS | From: [61.64.1.159] | 發表日期 : 2022-10-22 23:37

#include <iostream>
using namespace std ;
int main () {
    long long int N , L , tree = 0 , max = -1 ;
    cin >> N >> L ;
    int a[N+2] , b[N+2] ;
    a[N+1] = L ;
    a[0] = 0 ; b[0] = 0 ;
    for( int i = 1 ; i <= N ; i++ ) cin >> a[i] ;
    for( int j = 1 ; j <= N ; j++ ) cin >> b[j] ;
    
    bool flag = 1 ;
    while( flag ) {
        flag = 0 ;
        for( int i = 1 ; i <= N ; ) {
            if( a[i] + b[i] <= a[i+1] || a[i] - b[i] >= a[i-1] ){
                if( b[i] > max ) max = b[i] ;
                flag = 1 ;
                N -= 1 ;
                for( int j = i ; j <= N + 1 ; j++ ) {
                    a[j] = a[j+1] ;
                    b[j] = b[j+1] ;
                }
                tree++ ;
            } else {
                i++ ;
            }
        }
    }
    cout << tree << endl ;
    if( max == -1 ) cout << "0" << endl ;
    else cout << max << endl ;
    return 0 ;
}

 
ZeroJudge Forum