#14126: 用C寫的...可參考...P.S.我在搜直徑時用線性搜尋,沒想到這編譯器太...(TLE)我以為速度很快才對..所以改成二元搜尋T_T


HuangNO1 (雷姆醬)

School : 中南大学
ID : 60967
IP address : [1.163.103.108]
Last Login :
2021-04-06 19:35:03
c575. APCS 2017-0304-4基地台 -- 2017年3月APCS | From: [61.230.162.147] | Post Date : 2018-06-14 23:26

這題也沒人寫解題報告,最近在隨機寫一些APCS題...
我加一些注解好了
P.S.不喜歡這編譯器..狀況一堆

#include <stdio.h> int N_site[ 50001 ] ; //紀錄服務點位置 void swap( int *a , int *b ){ int tmp = *a ; *a = *b ; *b = tmp ; } void sot ( int N ) // 插入排序 { for ( int i = 0 ; i < N ; i ++ ) for ( int j = i ; j >= 0 ; j-- ) if ( N_site[ j ] < N_site[ j - 1 ] ) swap ( &N_site[ j ] , &N_site[ j - 1 ] ) ; } int try_1 ( int R , int N , int K ) //檢測直徑 { int num = 0 ; //num紀錄架設的基地台數,不能超過K int site ; // site紀錄直徑所到範圍 for ( int i = 0 ; i < N ; ){ //將i的進位主導權先拿走 site = N_site[ i ] + R ; //一個一個直徑慢慢擴大服務範圍 num += 1 ; // 增加一個基地台 if ( num > K ) // 基地台數超出K -> 不合格 (半徑太小->擴大) return 0 ; if ( N_site[ N - 1 ] <= site ) // 服務範圍到最後的服務點,且有直徑內縮(方向<-)可能(直徑太大) return 1 ; while( N_site[ i ] <= site ) //尋找下一個服務點,且超出目前基地台的服務範圍 i++ ; } } int main() { int r , R , r_R , N , K ; // r_R 是 r 與 R 的中間值 ( r->min , R->max ) while( scanf( "%d %d" , &N , &K ) != EOF ){ for ( int i = 0 ; i < N ; i++ ) scanf( "%d" , &N_site[ i ] ) ; sot( N ) ; if ( K == 1 ) R = N_site[ N - 1 ] - N_site[ 0 ] ; else { r = 1 ; //最小直徑 R = ( N_site[ N - 1 ] - N_site[ 0 ] / K ) + 1 ; //最大直徑 while ( try_1( R - 1 , N , K ) ){ r_R = ( r + R ) / 2 ; if ( try_1 ( r_R , N , K ) ) 直徑縮小 R = r_R ; else r = r_R + 1 ; // 擴大直徑 if ( r == R ) //兩直徑重和 break ; } } printf ( "%d\n" , R ) ; } return 0 ; }

.....寫注解好累..希望大家有看懂
 
#14127: Re:用C寫的...可參考...P.S.我在搜直徑時用線性搜尋,沒想到這編譯器太...(TLE)我以為速度很快才對..所以改成二元搜尋T_T


HuangNO1 (雷姆醬)

School : 中南大学
ID : 60967
IP address : [1.163.103.108]
Last Login :
2021-04-06 19:35:03
c575. APCS 2017-0304-4基地台 -- 2017年3月APCS | From: [61.230.162.147] | Post Date : 2018-06-14 23:31

忘了寫 執行結果 : AC 1s 260kb

 
#14317: Re:用C寫的...可參考...P.S.我在搜直徑時用線性搜尋,沒想到這編譯器太...(TLE)我以為速度很快才對..所以改成二元搜尋T_T


james.liu841@gmail.com (小貓貓)

School : 國立交通大學
ID : 67311
IP address : [49.159.0.48]
Last Login :
2021-08-25 11:46:11
c575. APCS 2017-0304-4基地台 -- 2017年3月APCS | From: [114.42.166.192] | Post Date : 2018-07-13 20:14

忘了寫 執行結果 : AC 1s 260kb



自己測試時輸入的側資,和真正用來評定的測資是差很多的,TLE應該不是編譯器問題

插入排序其實也很慢,內建的排序就很好用了

這是我做的小修改,8ms, 508KB

 

#include <algorithm>

#include <iostream>

 

using namespace std;

 

int N_site[50001];  //紀錄服務點位置

 

int try_1(int R, int N, int K)  //檢測直徑

{

    int num = 0;  //num紀錄架設的基地台數,不能超過K

    int site, i;  // site紀錄直徑所到範圍

 

    for (i = 0; i < N;) {      //將i的進位主導權先拿走

        site = N_site[i] + R;  //一個一個直徑慢慢擴大服務範圍

        num += 1;              // 增加一個基地台

        if (num > K)           // 基地台數超出K -> 不合格 (半徑太小->擴大)

            return 0;

        if (N_site[N - 1] <= site)  // 服務範圍到最後的服務點,且有直徑內縮(方向<-)可能(直徑太大)

            return 1;

        while (N_site[i] <= site)  //尋找下一個服務點,且超出目前基地台的服務範圍

            i++;

    }

}

int main() {

    cin.tie(0);

    ios_base::sync_with_stdio(0);

    int r, R, r_R, N, K, i;  // r_R 是 r 與 R 的中間值 ( r->min , R->max )

    while (cin >> N >> K) {

        for (i = 0; i < N; i++)

            cin >> N_site[i];

        sort(N_site, N_site + N);

        R = N_site[N - 1] - N_site[0];  //最大直徑

        if (K != 1) {

            r = 1;  //最小直徑

            while (try_1(R - 1, N, K)) {

                r_R = (r + R) / 2;

                if (try_1(r_R, N, K))  //直徑縮小

                    R = r_R;

                else

                    r = r_R + 1;  // 擴大直徑

                if (r == R)       //兩直徑重和

                    break;

            }

        }

        cout << R << '\n';

    }

    return 0;

}

 

 
ZeroJudge Forum