Kattis - Bus Numbers

題目

https://open.kattis.com/problems/busnumbers

給一個序列，如果有連續遞增 $1$ 的子序列 $a_i$ ~ $a_j$ 長度超過 $2$ ，那麼就可以化簡成 a_i-a_j

否則正常輸出每個數字

例如有一個序列 $(141, 142, 143, 145)$ 經過化簡後會變成 141-143 145

想法

可以化簡的是連續遞增的序列，那麼很容易可以想到先將序列排序

排序之後檢查每個連續的子序列長度，若超過 $2$ 就輸出化簡的結果，否則正常輸出即可

Code

//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int n, arr[1010];
	bool out=false;
	cin>>n;
	for(int i=0 ; i<n ; i++){
		cin>>arr[i];
	}
	sort(arr, arr+n);
	for(int i=1, cnt=1 ; i<=n ; i++){
		// 當 i==n 時是看到最後一個元素的時候
		// 此時直接進入輸出階段
		if(arr[i]-1 == arr[i-1] && i!=n){
			cnt++;
		}
		else{
			// 輸出之間要有空隔間格
			if(out) cout<<" ";
			else out=true;
			
			if(cnt>2){
				// 輸出化簡的結果
				cout<<arr[i-cnt]<<"-"<<arr[i-1];
			}
			else if(cnt==2){
				// 長度剛好為 2，將兩個元素都正常輸出
				cout<<arr[i-2]<<" "<<arr[i-1];
			}
			else{
				cout<<arr[i-1];
			}
			cnt=1;
		}
	}
	cout<<'\n';
	return 0;
}

複雜度分析

輸入時間複雜度為 $O(n)$

排序時間複雜度為 $O(nlogn)$

遍歷時間複雜度為 $O(n)$

總時間複雜度為 $O(n + nlogn)$