题意:
数轴上有 n 个闭区间 [ai, bi],选择尽量少的区间覆盖一条指定线段 [1, t]中的所有整点。
不可能办到输出-1
输入:
注意,输入包含多组测试数据,请处理到文件结束
第一行:N和T
第二行至N+1行: 每一行一个闭区间。
输出:
选择的区间的数目,不可能办到输出-1
输入样例:
3 10
1 7
3 6
6 10
输出样例:
2
解题思路:
这道题目的贪心条件在于区间左端点要小于当前待覆盖区间的左端点,这个条件下,同时尽可能选择右端点更大的区间,因为这样直观上可以尽可能保证取最少的区间完成题目上的覆盖要求。用pair类型的vector动态数组方便记录所有的区间,然后重写cmp函数方便对每个区间按照要求进行排序,按顺序对已有区间进行遍历,在区间左端点要小于当前待覆盖区间的左端点的条件下,找寻右端点最大的区间作为要选择的覆盖区间,因为题目只求区间个数,只需对num自增即可。若在覆盖完成前已经不存在这样的区间了,就及时break,输出-1代表无解,否则输出num。
注意事项:
1、一定注意这里的覆盖是指整点覆盖,即只需要覆盖所有的整数,最开始因为这一点wa了很多次。
2、最开始区间左端点不要设成1,应该设成0,因为for循环中的判断条件因为第一点的原因会需要给line.first加一。
总结:
依然是典型的贪心策略的选择问题,这道题本身难度不大,但易错点挺多的,有部分也因为题目描述不是太清楚,然后所有的贪心类问题都不太好有一个 固定的思维,没有办法固定地找出一个贪心策略,只有多练习多总结,培养这方面的悟性和灵感。
参考代码:

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;
int flag,n,num;
int t,x,y;
vector<pair<int, int> >v;//存储所有的区间
pair<int, int> line;//存储那条线段
bool cmp(pair<int, int> a,pair<int, int> b){//按照左端点排序
    if(a.first!=b.first)
    return  a.first<b.first;
    else return a.second>b.second;
}
int main(int argc, const char * argv[]) {
    while (~scanf("%d%d",&n,&t)) {
        num=0;flag=0;line.first=0;//num:区间个数即答案,flag:判断是否有解
        v.clear();
        while (n--) {
            scanf("%d%d",&x,&y);
            v.push_back(pair<int, int>(x,y));
        }
        line.second=t;
        int cur=line.first;                    
        sort(v.begin(), v.end(), cmp);
        for (int i=0; i<v.size(); i++) {
            if(v[i].first<=line.first+1){
                while (i<v.size()&&v[i].first<=line.first+1) {
                    if(v[i].second>cur){
                        cur=v[i].second;
                    }
                    i++;
                }
            }
            else{
                flag=1;//no method
                break;
            }
            num++;
            if(cur>=line.second){
                break;}
            line.first=cur;
            i--;
        }
        if(flag==0&&cur>=line.second)printf("%d\n",num);
        else {printf("-1\n");}
    }
    return 0;
}

Logo

魔乐社区(Modelers.cn) 是一个中立、公益的人工智能社区,提供人工智能工具、模型、数据的托管、展示与应用协同服务,为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作,由全产业链共同建设、共同运营、共同享有,推动国产AI生态繁荣发展。

更多推荐