這題也沒人寫解題報告,最近在隨機寫一些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 ;
}

.....寫注解好累..希望大家有看懂

忘了寫 執行結果 : 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;

}

如果換成泡沫排序法可以嗎？

如果換成泡沫排序法可以嗎？

一樣慢