Koios1143的筆記

Kattis - Planting Trees

發表於 分類於

Kattis - Planting Trees

題目

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

有一個園丁要種樹，每棵樹要花上一天的時間播種，並且因為園丁很懶惰，所以一天只會播種一棵樹的種子

聰明的園丁已經知道每棵樹會花幾天成長完成，並且園丁可以自己選擇每顆樹種下的順序

園丁想知道最後一顆樹成長完成的隔天是第幾天(從 1 開始計算)

輸入包含一個正整數 $N$，接下來有 $N$ 個正整數 $t_i$ 表示每棵樹的成長時間

$1 \leq N \leq 100000 \quad 1 \leq t_i \leq 1000000$

想法

因為題目當中只有限制每天只能種一棵樹，但是並沒有限制要一顆樹完全成長後才能繼續種植，所以最佳解很顯然的是要從 $t_i$ 最大的樹開始種植

也就是說我們先依照種植時間由大到小排序，接下來模擬整個種樹的情況

記錄下當前剩餘成長日的最大值 $M$

若 $t_i > M$，就將 $M$ 更新成 $t_i$

而每一輪的模擬都需要將 $M$ 遞減，並且將答案遞增

詳細來說，我們的步驟是這樣

  1. 輸入資料
  2. 將資料由大到小排序
    這部分也可以由小到大排序，後面遍歷從後面往前面走即可
  3. 紀錄當前最大剩餘成長日 $M$ 為第 $1$ 個元素
  4. 因為每棵樹第一天都要先種植，答案先預設為 $1$
  5. 模擬接下來的 $n-1$ 天
    • 每天將 $M$ 遞減
    • 每天將答案遞增
    • 如果 $t_i > M$
      • 更新 $M = t_i$
  6. 最後答案加上剩餘的 $M$ 再加上 $1$ 表示隔天

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int n, arr[100010];
	cin>>n;
	for(int i=0 ; i<n ; i++){
		cin>>arr[i];
	}
	sort(arr, arr+n);
	// 由小到大排序，所以由後往前取元素
	int days=arr[n-1], ans=1;
	for(int i=n-2 ; i>=0 ; i--, ans++){
		days--;
		if(arr[i] > days)
			days = arr[i];
	}
	ans += (days+1);
	cout<<ans<<"\n";
	return 0;
}

複雜度分析

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

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

遍歷所有成長時間的時間複雜度為 $O(n)$

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