牛客 切长条 (贪心)

题目描述
给定如图所示的若干个长条。你可以在某一行的任意两个数之间作一条竖线,从而把这个长条切开,并可能切开其他长条。问至少要切几刀才能把每一根长条都切开。样例如图需要切两刀。

注意:输入文件每行的第一个数表示开始的位置,而第二个数表示长度。
输入描述:
Line 1: A single integer, N(2 <= N <= 32000)
Lines 2…N+1: Each line contains two space-separated positive integers that describe a leash. The first is the location of the leash’s stake; the second is the length of the leash.(1 <= length <= 1e7)

输出描述:
Line 1: A single integer that is the minimum number of cuts so that each leash is cut at least once.
示例1
输入

7
2 4
4 7
3 3
5 3
9 4
1 5
7 3

输出
2

  • 首先每条线段按照左端点升序排列
  • 然后开始遍历,只要新的线段的左端点大于之前线段中右端点最小的端点,那么就没有重合部分,就要多砍一刀
  • 否则就更新最右端的最小值,并且继续遍历
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e7 + 5;

struct node
{
   
    int l, r;
    bool operator<(const node x)
    {
   
        return l < x.l;
    }
} a[maxn];

int main()
{
   
    int n, len;
    while (~scanf("%d", &n))
    {
   
        for (int i = 1; i <= n; ++i)
        {
   
            scanf("%d%d", &a[i].l, &len);
            a[i].r = a[i].l + len;
        }
        sort(a + 1, a + n + 1);
        int minn = a[1].r;
        int ans = 1; //至少砍一刀
        for (int i = 2; i <= n; ++i)
        {
   
            if (a[i].l >= minn)
            {
   
                ++ans;
                minn = a[i].r;
            }
            else
                minn = min(minn, a[i].r);
        }
        printf("%d\n", ans);
    }
}
先爱己,后爱人,而后被爱~
全部评论

相关推荐

无敌战神大菜鸡:计算机来卷嵌入式?疯啦
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
01-06 15:18
百度 底层软硬件开发 28*16+4 硕士211
贴心的莲雾向光而行:感觉理想更好,百度这家公司没啥未来
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务