Koios1143的筆記

Kattis - Sticky Situation

發表於 分類於

Kattis - Sticky Situation

題目

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

給定 $N$ 個正整數數字 $n$，求是否有任三個數字能組成三角形 ($a+b>c$)

$3 \leq N \leq 20000 \quad 1 \leq n \leq 2^{60}$

想法

對於一群無序的序列，可以觀察看看排序後是否有好的性質

在這一題當中，我們要試圖找到 $a, b, c$，其中 $a \leq b \leq c$ 且 $a + b > c$

前提條件當中的 $a \leq b \leq c$ 可以直接透過由小到大排序解決

接下來也許你會想到，我們可以由小到大枚舉三角形的三邊長，然後判斷是否符合

但是真的有必要枚舉所有情況嗎?

假如我們先選擇了三個不連續的數字 $i, i+a, i+b \ (a < b)$

如果說這三個不連續的數字能形成三角形，因為是遞增序列，可以保證 $i+(a-1), i+a, i+b$ 也一定會成立

同理， $i+(b-2), i+(b-1), i+b$ 也會成立

用更簡單的方式來說，我們只需要去枚舉連續的三個元素是否符合即可

也就是只需要檢查 $i, i+1, i+2$ 即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int n;
	long long arr[20010];
	cin>>n;
	for(int i=0 ; i<n ; i++){
		cin>>arr[i];
	}
	sort(arr, arr+n);
	bool possible=false;
	for(int i=0 ; i<n-2 ; i++){
		if(arr[i] + arr[i+1] > arr[i+2]){
			possible=true;
			break;
		}
	}
	if(possible) cout<<"possible\n";
	else cout<<"impossible\n";
	return 0;
}

複雜度分析

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

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

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

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