C语言贪心算法之找点

青旅半醒 2022-06-04 01:40 150阅读 0赞

## 找点 ##

时间限制：2000 ms  |  内存限制：65535 KB

难度：2

描述

上数学课时，老师给了LYH一些闭区间，让他取尽量少的点，使得每个闭区间内至少有一个点。但是这几天LYH太忙了，你们帮帮他吗？

输入

多组测试数据。  
每组数据先输入一个N，表示有N个闭区间（N≤100)。  
接下来N行，每行输入两个数a，b(0≤a≤b≤100），表示区间的两个端点。

输出

输出一个整数，表示最少需要找几个点。

样例输入

4
    1 5
    2 4
    1 4
    2 3
    3
    1 2
    3 4
    5 6
    1
    2 2

样例输出

1
    3
    1

#include<stdio.h>
    #include<algorithm>
    using namespace std;
    struct dian
    {
        int left;
        int right;
    } a[101];
    int cmp(dian x,dian y)//将右边按从小到大排序
    {
        if(x.left!=y.left)
            return x.left<y.left;
        return x.right<y.right;
    }
    int main()
    {
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            int i,j,ans=1;
            for(i=0; i<n; i++)
                scanf("%d%d",&a[i].left,&a[i].right);
            sort(a,a+n,cmp);
            for(i=n-1,j=n-2; j>=0;)
            {
                if(a[j].right<a[i].left)//如果右端点小于下一个的左端点，数目加一
                {
                    ans++;
                    i=j;//将值赋给原来的点，重新进行比较
                }
                j--;
            }
            printf("%d\n",ans);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，150人围观）

还没有评论，来说两句吧...

相关阅读

相关 C语言经典贪心算法之加油站问题（详解）

文章目录一、贪心算法二、加油站问题一、贪心算法贪心算法暗示一种不追求最优解，只希望找到较为满意解的方法。贪心算法省去了为找最优解

ゝ一纸荒年。/ 2023年01月11日 01:27/ 0 赞/ 251 阅读

相关汽车加油问题贪心算法c语言,汽车加油问题之贪心算法（全面分析）

一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。给出N，并以数组的形式给出加油站的个数及相

柔光的暖阳◎/ 2022年10月15日 05:55/ 0 赞/ 210 阅读

相关贪心算法解决找零钱问题

4.1 找零问题问题描述：设有50、20、10、5、1、0.5、0.1等面额的零钱，顾客购物花了n元，在支付（n / 100 + 1） \ 100元后，收银员应如

Dear 丶/ 2022年06月07日 04:22/ 0 赞/ 376 阅读

相关 C语言贪心算法之喷水装置（二）

喷水装置（二）时间限制：3000 ms | 内存限制：65535 KB 难度：4 描述有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(

ゞ浴缸里的玫瑰/ 2022年06月04日 06:41/ 0 赞/ 158 阅读

相关 C语言贪心算法之非洲小孩

非洲小孩时间限制：1000 ms | 内存限制：65535 KB 难度：2 描述家住非洲的小孩，都很黑。为什么呢？第一，他们地处热带，太阳辐射严重。

灰太狼/ 2022年06月04日 01:40/ 0 赞/ 161 阅读

相关 C语言贪心算法之找点

找点时间限制：2000 ms | 内存限制：65535 KB 难度：2 描述上数学课时，老师给了LYH一些闭区间，让他取尽量少的点，使得每个闭区间内至少有一

青旅半醒/ 2022年06月04日 01:40/ 0 赞/ 151 阅读

相关 C语言贪心算法之过河问题

过河问题时间限制：1000 ms | 内存限制：65535 KB 难度：5 描述在漆黑的夜里，N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的

骑猪看日落/ 2022年06月03日 22:47/ 0 赞/ 206 阅读

相关 C语言之贪心算法疯牛

疯牛时间限制：1000 ms | 内存限制：65535 KB 难度：4 描述农夫 John 建造了一座很长的畜栏，它包括N (2 <= N <= 10

喜欢ヅ旅行/ 2022年06月03日 00:10/ 0 赞/ 153 阅读

相关 C语言贪心算法之贪婪的老鼠

Greedy Mouse 时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述 A fat mouse prepared M poun

忘是亡心i/ 2022年06月02日 07:24/ 0 赞/ 165 阅读

相关贪心算法之钱币找零问题

贪心算法一、基本概念：所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上

青旅半醒/ 2022年05月18日 23:59/ 0 赞/ 344 阅读