题解 | #校门外的树#

校门外的树

https://ac.nowcoder.com/acm/problem/16649

经典老题了,之前一直用线段树,直到知道了差分。。。
题目是0到n都种了一个树,可以考虑偏移一位,1到n+1种了一个树
l到r区间-1即可直接利用差分数组,求一遍前缀和即可得到原数组,等于1的代表没有被砍掉

#include<iostream>
using namespace std;
int a[10010];
int main()
{
    int n,k;
    cin>>n>>k;
    a[1]=1;
    a[n+2]=-1;
    while(k--)
    {
        int l,r;
        cin>>l>>r;
        l++,r++;
        a[l]--;
        a[r+1]++;
    }
    for(int i=1;i<=n+1;i++)
        a[i]+=a[i-1];
    int ans=0;
    for(int i=1;i<=n+1;i++)
        if(a[i]>=1)
            ans++;
    cout<<ans<<endl;
}
全部评论

相关推荐

太难了,双9bg也被刷
投递韶音科技等公司10个岗位
点赞 评论 收藏
分享
07-23 11:23
门头沟学院 Java
点赞 评论 收藏
分享
07-19 13:28
长沙学院 Java
程序员小白条:你有面试就有希望,没面试自然就没希望,到时候就知道了,你问别人也没啥用处的
点赞 评论 收藏
分享
06-11 14:15
已编辑
门头沟学院 后端
田心今心:打招呼改一下,把实习半年以上随时到岗放第一行,因为ssob的hr不点击看的时候只能看前面几个字,你前面几个字hr获取不到什么信息,也就不会点进来看
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务