發表新討論
#14125: ...為啥一直TLE,請較高人指導


HuangNO1 (雷姆醬)

學校 : 中南大学
編號 : 60967
來源 : [103.156.242.195]
最後登入時間 ：
2023-12-03 15:57:20
c575. APCS 2017-0304-4基地台 -- 2017年3月APCS | From: [61.230.162.147] | 發表日期 : 2018-06-14 22:51 
#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 ;
	int site ;
	
	for ( int i = 0 ; i < N ; ){
		site = N_site[ i ] + R ;
		num += 1 ;
		if ( num > K )
			return 0 ;
		if ( N_site[ N - 1 ] <= site )
			return 1 ;
		while( N_site[ i ] <= site )
			i++ ;
	}
}
int main()
{
	int R , N , K ;
	while( scanf( "%d %d" , &N , &K ) != EOF ){
		for ( int i = 0 ; i < N ; i++ )
			scanf( "%d" , &N_site[ i ] ) ;
		sot( N ) ;
		
		R = N_site[ N - 1 ] - N_site[ 0 ] ;
		while ( try_1( R - 1 , N , K ) )
			R-- ;
		printf ( "%d\n" , R ) ;
	}
	return 0 ;
}
 
#35313: Re: ...為啥一直TLE,請較高人指導


luray0601@gmail.com (QWERTYPIG)

學校 : 臺北市私立復興實驗高級中學
編號 : 139334
來源 : [36.226.26.217]
最後登入時間 ：
2023-03-24 20:42:11
c575. APCS 2017-0304-4基地台 -- 2017年3月APCS | From: [203.72.177.253] | 發表日期 : 2023-05-25 08:40 
#include 
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 ;
	int site ;
	
	for ( int i = 0 ; i < N ; ){
		site = N_site[ i ] + R ;
		num += 1 ;
		if ( num > K )
			return 0 ;
		if ( N_site[ N - 1 ] <= site )
			return 1 ;
		while( N_site[ i ] <= site )
			i++ ;
	}
}
int main()
{
	int R , N , K ;
	while( scanf( "%d %d" , &N , &K ) != EOF ){
		for ( int i = 0 ; i < N ; i++ )
			scanf( "%d" , &N_site[ i ] ) ;
		sot( N ) ;
		
		R = N_site[ N - 1 ] - N_site[ 0 ] ;
		while ( try_1( R - 1 , N , K ) )
			R-- ;
		printf ( "%d\n" , R ) ;
	}
	return 0 ;
}

排序建議不要用bubble_sort，效率太差，要改用如merge_sort會內建等複雜度O(nlogn)的演算法

 
ZeroJudge Forum