h028 - 202001_3 砍樹
題目描述
題目描述了在一個長條型林場中砍樹的問題。林場中有 N 棵樹，每棵樹都有座標和高度。砍樹的條件是：樹倒下時不會超出林場範圍，也不會壓到其他尚未砍除的樹木。目標是計算能砍除的樹木數量，以及這些樹木中的最高高度。
解題思路
本題採用貪心策略。首先，將所有樹的座標存入一個集合 s 中，並使用 map 儲存每個座標對應的高度。使用隊列 q 儲存樹的座標和高度。
每次從隊列中取出一個樹，判斷其左右倒下的範圍內是否有其他樹。如果沒有，則將該樹砍倒，並將其左右鄰居加入隊列。同時更新砍倒的樹木數量和最大高度。
使用集合 s 可以快速查詢指定範圍內是否存在其他樹。
複雜度分析
- 時間複雜度: O(N log N)。主要時間花在集合的插入、刪除和查找操作上，這些操作的時間複雜度都是 O(log N)。隊列的操作和 map 的操作也都是 O(log N)。
- 空間複雜度: O(N)。需要儲存所有樹的座標、高度以及隊列中的樹。
程式碼
#include <iostream>
#include <queue>
#include <set>
#include <map>
using namespace std;
long long n,l,ans,a[100005][2],amax;
map <long long,long long> mp;
queue <pair <long long,long long>> q;
set <long long> s;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> l;
s.insert(0);
mp[0]=mp[l]=1e10;
s.insert(l);
for(int i=0;i<n;++i){
cin >> a[i][0];
s.insert(a[i][0]);
}
for(int i=0;i<n;++i){
cin >> a[i][1];
mp[a[i][0]]=a[i][1];
q.push(make_pair(a[i][0],a[i][1]));
}
while(q.empty()==0){
pair <long long,long long> p=q.front();
q.pop();
if(s.count(p.first)==0)continue;
long long lft=*(--s.find(p.first)),rgt=*(++s.find(p.first));
//cout << lft << " " << rgt << "\n";
if(lft<=p.first-p.second||rgt>=p.first+p.second){
++ans;
amax=max(amax,p.second);
s.erase(p.first);
q.push(make_pair(lft,mp[lft]));
q.push(make_pair(rgt,mp[rgt]));
}
}
cout << ans << "\n" << amax;
}