【題目敘述】http://judge.epass2u.com/problem/APCS1090105-3 (無法使用)
【解題想法】
- 函式 cut_tree( )：決定一棵樹可不可以砍。
- (Line-13)：檢查樹倒下後，會不會超出邊界？
- (Line-15/17)：找出左邊第一棵和右邊第一棵還沒有砍的樹。
- set <int> tree; 紀錄已經砍下的樹的高度。
- cut[ i ]：紀錄第 i 棵樹是否已經被砍了。
- (Line-46)：如果這一輪有砍新的樹，則需再檢查一輪，看有沒有還可以砍的樹。
- (Line-50)：輸出所有砍下的樹中，高度最高的。
#include <iostream>
#include <set>
using namespace std;
const int maxn = 1000005;
int n, l;
int X[maxn], H[maxn];
int cut[maxn];
int ans, pre;
bool flag;
set <int> tree;
void cut_tree(int i){
if (X[i] - H[i] >= 0 || X[i] + H[i] <= l){
int L = i - 1;
while (L > 0 && cut[L] == 1) L--;
int R = i + 1;
while (R < n - 1 && cut[R] == 1) R++;
if ((i > 0 && X[i] - H[i] >= X[L]) || (i < n-1 && X[i] + H[i] <= X[R])){
ans++;
cut[i] = 1;
tree.insert(H[i]);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> l;
for (int i=0; i<n; i++){
cin >> X[i];//在數線上的位置, 0~l
}
for (int i=0; i<n; i++){
cin >> H[i];//樹高
}
ans = 0;
pre = 0;
flag = true;
while (flag){
for (int i=0; i<n; i++){
if (cut[i] == 0){
//第 i 棵樹還沒砍
cut_tree(i);
}
}
flag = (ans != pre);//這一輪砍了新的樹
pre = ans;
}
cout << ans << '\n';
if (tree.size()) cout << *(--tree.end()) << '\n';
else cout << "0\n";
return 0;
}
Python code (credit: Amy Chou)
def cut_tree(i):
global ans, cut, tree
if X[i] - H[i] >= 0 or X[i] + H[i] <= l:
L = i - 1
while L > 0 and cut[L] == 1:
L -= 1
R = i + 1
while R < n - 1 and cut[R] == 1:
R += 1
if (i > 0 and X[i] - H[i] >= X[L]) or (i < n - 1 and X[i] + H[i] <= X[R]):
ans += 1
cut[i] = 1
tree.append(H[i])
# main program
n, l = map(int, input().split())
X = list(map(int, input().split()))
H = list(map(int, input().split()))
ans = 0
pre = 0
flag = True
cut = [0 for _ in range(n)]
tree = []
while flag:
for i in range(n):
if cut[i] == 0:
cut_tree(i)
if ans == pre:
flag = False #這一輪沒砍新樹
else:
flag = True #這一輪砍了新的樹
pre = ans
print(ans)
if (len(tree) > 0):
print(max(tree))
else:
print(0)