jimore

用户名：uq_30465888842

访问量：8225

签　名：

Don't let the dream just be a dream!!!

等　　级
排　　名	179
经　　验	6664
参赛次数	29
文章发表	63
年　　龄	0
在职情况	学生
学　　校	四川农业大学
专　　业	计算机科学与技术

　　自我简介：

目标院校：上海交通大学

TA的其他文章

二分答案（简单理解）
浏览：373

求一个很大的数的所有质因子（新方法）
浏览：204

佩尔方程——模板题
浏览：175

你可能喜欢

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

线段和点（很容易理解）

　　作者: jimore　　　　发表时间：2022-02-04 10:14:11 浏览：369　|　评论：1　

原题链接：蓝桥杯算法提高VIP-线段和点

###方法
先将线段按左端点升序排列，再按右端点降序排列
![](/image_editor_upload/20220204095807_31280.jpg)
这样排序，就只需看哪个点在线段上走得最远就能确定哪个点覆盖最多的线段了，就取它放进自己的点集中
```c++
bool cmp(Node x,Node y){
    if(x.l==y.l){
        return x.r>y.r;
    }
    return x.l<y.l;
}
```
再定义一个指针指向线段数组的开始位置
```c++
start=0;
```
然后再不断地枚举点，看看哪个点能覆盖最多的线段（即能让start最靠近线段数组的末尾）
```c++
while(start<m){
    far=0;
    for(int i=0;i<n;i++){
        if(dots[i]>=blocks[start].l){
            for(int j=start;j<m;j++){
                if(dots[i]<blocks[j].l||dots[i]>blocks[j].r){
                    far=max(far,j);//更新本次的最远位置
                    break;
                }else if(dots[i]>=blocks[j].l&&dots[i]<=blocks[j].r){
                    far=max(far,j+1);
                }
            }
        }
    }
	start=far;// 取走得最远的位置作为下一次的起始位置
    ans++;//没进行一次操作让ans++，asn的值代表选的线段的条数
}
```
最终打印ans
```c++
cout<<ans<<endl;
```
###完整代码
```c++
#include <bits/stdc++.h>
using namespace std;
typedef struct node{
    int l,r;
}Node;
bool cmp(Node x,Node y){
    if(x.l==y.l){
        return x.r>y.r;
    }
    return x.l<y.l;
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<int>dots;
    vector<Node>blocks;
    for(int i=0;i<n;i++){
        int dot;
        cin>>dot;
        dots.push_back(dot);
    }
    for(int i=0;i<m;i++){
        Node block;
        cin>>block.l>>block.r;
        blocks.push_back(block);
    }
    sort(dots.begin(),dots.end());
    sort(blocks.begin(),blocks.end(),cmp);
    int ans=0,start=0,far;
    while(start<m){
        far=0;
        for(int i=0;i<n;i++){
            if(dots[i]>=blocks[start].l){
                for(int j=start;j<m;j++){
                    if(dots[i]<blocks[j].l||dots[i]>blocks[j].r){
                        far=max(far,j);
                        break;
                    }else if(dots[i]>=blocks[j].l&&dots[i]<=blocks[j].r){
                        far=max(far,j+1);
                    }
                }
            }
        }
        start=far;
        ans++;
    }
    cout<<ans<<endl;
    //system("pause");
    return 0;
}
```

0.0分

5 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

早起床

大家不要被误导了，区间排序的第二个数是大的在前面还是小的在前面，都是正确的，关键是要自己理解题意，然后理解代码的for循环的顺序

2022-10-19 21:03:17

jimore

TA的其他文章

你可能喜欢

统计字符（C语言描述运用ctype.h）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

字符串输入输出函数（Java代码）

C语言训练-角谷猜想（C语言代码）

线段和点（很容易理解）

评论区

精彩推荐

简单的a+b （C++语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

母牛的故事（C语言代码）

良心推荐——>题解1049：C语言程序设计教程（第三版）课后习题11.1 （C语言描述——简单明了，时间复杂度低）

神奇的fans （C语言代码）

班级人数（C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

jimore

TA的其他文章

你可能喜欢

统计字符 （C语言描述运用ctype.h）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

字符串输入输出函数 （Java代码）

C语言训练-角谷猜想 （C语言代码）

线段和点（很容易理解）

评论区

精彩推荐

简单的a+b （C++语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

母牛的故事 （C语言代码）

良心推荐——>题解1049：C语言程序设计教程（第三版）课后习题11.1 （C语言描述——简单明了，时间复杂度低）

神奇的fans （C语言代码）

班级人数 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

统计字符（C语言描述运用ctype.h）

字符串输入输出函数（Java代码）

C语言训练-角谷猜想（C语言代码）

　　评论区

母牛的故事（C语言代码）

班级人数（C语言代码）