题解：AT_nikkei2019_final_d Deforestation

xyx404 · 2024-09-16 19:37:51 · 题解

题目：

在我写题解时题目翻译有错误，故此处放上简略的正确翻译。

有 N 根竹子，编号从 1 到 N。初始时，所有竹子的高度是 0，时间每过一秒，每根竹子的高度增加 1。

有 M 个砍伐计划，第 i 个计划在 T_i 时，将砍掉编号在 L_i 和 R_i 之间的竹子。当竹子砍下时高度为 x 时，会得到 x 的竹子。被砍掉的竹子高度将变为 0，之后还会生长。

求可以得到多少竹子。

完整题目，点击此处。

思路：

因为每过一秒高度都会增加一，且砍后会继续生长，所以我们可以只计算第 i 个竹子最后是在什么时候被砍掉的，这个时间就是这个竹子的高度。

实现，在输入后我们可以直接从最后开始向前遍历，因为题目满足输入的时间 T_i 一定小于等于 T_{i+1}。

定义一个 set，类型为 int，名字叫 se，用来标记这个竹子有没有砍过。

用 lower_bound 函数查找在 se 里第一个大于等于 L_i 的值的位置，然后遍历编号在 L_i 和 R_i 之间的竹子，加上现在的时间也就是可以从竹子身上得到的竹子，并把这个竹子从 se 里删除。

代码：

#include<bits/stdc++.h>
using namespace std;
set<int>se;
int n,m;
int t[200005],l[200005],r[200005];
long long ans=0;
void solve(){
    for(int i=1;i<=n;i++)se.insert(i);// 记录有没有砍 
    for(int i=m;i>=1;i--){
        auto it=se.lower_bound(l[i]);// 二分查找第一个大于等于 l[i] 的值的位置
        while(it!=se.end()&&*it<=r[i]){
            ans+=t[i];
            se.erase(it++);
        }
    }
    cout<<ans<<"\n";
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>t[i]>>l[i]>>r[i];
    }
    solve();
    return 0;
}