Koios1143的筆記

Zerojudge b964

發表於 更新於 分類於 ，

Zerojudge b694

題敘

https://zerojudge.tw/ShowProblem?problemid=b964
給定 $n$ 個成績，求成績排序後結果、不及格中最高分、及格中最低分

想法

排序可以直接用STL sort解決
其他可以拿兩個變數紀錄即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//By Koios1143
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
int n,arr[1000],lucky=999,unlucky=-1;
int main(){
	IOS
	cin>>n;
	for(int i=0 ; i<n ; i++){
		cin>>arr[i];
		if(arr[i]>=60)
			lucky = min(lucky,arr[i]);
		else
			unlucky = max(unlucky,arr[i]);
	}
	sort(arr,arr+n);
	for(int i=0 ; i<n ; i++){
		if(i)
			cout<<" ";
		cout<<arr[i];
	}
	cout<<"\n";
	if(unlucky == -1)
		cout<<"best case\n";
	else
		cout<<unlucky<<"\n";
	if(lucky==999)
		cout<<"worst case\n";
	else
		cout<<lucky<<"\n";
	return 0;
}

複雜度

找尋lucky number及unlucky number複雜度為 $O(n)$
sort複雜度為 $O(nlogn)$
總複雜度 $O(n+nlogn)$