切长条(贪心 思维)

题目

题目大意和思路:

这道题,其实就是经典的贪心问题——区间覆盖,我当时被迷惑了。就是找多少个两两不相交的区间。
按照结束位置先后排个序就行
有不懂的欢迎留言

AC代码:

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e8+9;
struct node
{
   
    int s;
    int l;
}c[maxn];
bool cmp(node a,node b)
{
   
    return a.l<b.l;
}
int main()
{
   
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
   
        cin>>c[i].s>>c[i].l;
        c[i].l = c[i].s + c[i].l;
    }
    sort(c,c+n,cmp);
    int en = 0;
    int st = 0;
    en = c[0].l;
    int  cnt = 1;
    for(int i=1;i<n;i++)
    {
   
        if(c[i].s>=en)
        {
   
            cnt++;
            st = c[i].s;
            en = c[i].l;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

全部评论

相关推荐

06-06 03:40
已编辑
电子科技大学 Java
在秋招的小白菜很想养修勾:一眼 苍穹外卖+谷粒商城,项目换一换吧,可以找一些付费知识星球博主带带,避免烂大街。多投投大厂,背背八股,你这学历乱杀了,等实习经验到位,到时候大厂闭眼选
投递美团等公司8个岗位
点赞 评论 收藏
分享
Cherrycola01:0实习 0项目 约等于啥也没有啊 哥们儿这简历认真的吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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