codeforces 1000C [经典题目]【排序,数据结构】

据说是一个非常经典的题目,我竟然疑似第一次做,emmmm,看来还是题目做的太少,也是学习太不系统了【毕竟靠自己摸索。。。】

题目分析:给你n个区间,问你区间中被覆盖的次数恰好为K的点的个数有多少个
对于每一个k 属于[1…n] 输出这样的点的个数
我们随意画一个图,就可以发现,如果我们将所有点都进行排序,然后遇到左端点就+1,遇到右端点就-1,这样我们就可以得到每一个区间的此时的覆盖数,这样跑完所有点就可以求出区间了,我们要注意的是,如果右端点记录的时候,采用 r+1来算的话,就可以直接将区间包括在内,这样会简化对于整点的计算

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
using namespace std;
const int maxn=1e5+50;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
typedef long long ll;
typedef pair<ll,ll> E;
vector<E>a;
ll ans[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    cl(ans);
    for(int i=1;i<=n;i++)
    {
        ll x,y;
        cin>>x>>y;
        a.push_back({x,1});
        a.push_back({y+1,-1});
    }
    sort(a.begin(),a.end());
    int now=0;
    for(int i=1;i<a.size();i++)
    {
        now+=a[i-1].second;
        ans[now]+=a[i].first-a[i-1].first;

    }
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<" ";
    }

    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 16:15
我应届生,去年10月份开始在这家公司实习,到今年10月份正好一年想(实习+试用期),在想要不要提前9月份就离职,这样好找工作些,但又差一个月满一年,又怕10月份国庆回来离职,容易错过了下半年的金九银十,到年底容易gap到年后
小破站_程序员YT:说这家公司不好吧,你干了快一年 说这家公司好吧,你刚毕业就想跑路说你不懂行情吧,你怕错过金九银十说 你懂行情吧,校招阶段在实习,毕业社招想换工作 哥们,我该怎么劝你留下来呢
应届生,你找到工作了吗
点赞 评论 收藏
分享
屌丝逆袭咸鱼计划:心态摆好,man,晚点找早点找到最后都是为了提升自己好进正职,努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累,大四学长有的秋招进的也不妨碍有的春招进,人生就这样
点赞 评论 收藏
分享
05-23 20:31
已编辑
武汉大学 Java
内向的柠檬精在研究求...:注意把武大标粗标大 本地你俩不是乱杀
实习进度记录
点赞 评论 收藏
分享
榕城小榕树:1200单休,我去干点啥别的不好
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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