当前位置:首页 > C++知识 > 正文内容

【贪心】区间选点

亿万年的星光5年前 (2021-02-02)C++知识2031

【题目描述】

数轴上有n个闭区间[ai, bi],取尽量少的点,使得每个区间内都至少有一个点。(不同区间内含的点可以是同一个,1<=n<=10000,1<=ai<=bi<=10^9)。求最少点的个数。

【输入】

n

n项工作的开始与结束时间

【输出】

最多参与的工作项数

【输入样例1】

Bash
4
3 13
6 20
4 14
1 10

【输出样例1】

1



【输入样例2】

Bash
3
4 7
6 8
11 20

【输出样例2】

2


【题目原型分析】

参考下图模型:

                                    

或者下图这种模型:

                                        


关于至少有一个点的解释:如果区间i内已经有一个点被取到,则称此区间已经被满足(闭区间)。

【解题思路】

首先考虑如果两个区间一个区间包含另外一个,小区间内的点一定在大区间内,但是大区间内的点不一定在小区间内。所以此时,只需要考虑较小的区间。当两个区间不包含但有重叠部分时,选择一个点在b_i更小的区间的最末端,则该点一定包含在两个区间内。我们的对不同区间的排序方式(即贪心准则)是按b_i从小到大i排序所有的区间,当b_i相同时则按照a_i从大到小进行排序。这样排序以后即使有包含的区间,小区间也一定会排在前面。接下来取第一个区间的最后一个点,然后向后查找第一个不包含该点的区间,取该区间的最后一个点,以此类推直到结束。

总结:

首先考虑区间包含的情况,当小区间被满足时大区间一定被满足。所以我们应当优先选取小区间中的点,从而使大区间不用考虑。按照上面的方式排序后,如果出现区间包含的情况,小区间一定在大区间里。所以此情况下我们会优先选择小区间。”


【参考代码】

#include<bits/stdc++.h>
using namespace std;
const int maxn=10010;
struct Node{
	int begin; //开始的点 
	int end; //结束的点 
}node[maxn];
bool cmp(Node a,Node b)
{
    return a.end<b.end;  //由小到大排序 
}
int main()
{
    int n,ans;
    while(scanf("%d",&n))
    {
        for(int i=0;i<n;++i)//输入区间 并处理
        {
            scanf("%d %d",&node[i].begin,&node[i].end);
        }
        sort(node,node+n,cmp);//将区间按右端点排序,右端点小的在前面
        ans=0;
        int position=-1;//pos代表第一个区间选取的点
        for(int i=0;i<n;++i)
        {
            if(node[i].begin>position)
            {
                position=node[i].end;
                ++ans;
            }
        }
        printf("%d\n",ans);
    }
}



其次,用队列的方式也可以做


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp (pair<int, int> &a,pair<int, int> &b){
    return a.second<b.second ? true:a.second==b.second&&a.first>b.first;
}
int main(int argc, const char * argv[]) {
    int n;cin>>n;
    vector<pair<int, int> > v;
    int x,y;
    while (n--) {
        cin>>x>>y;
        v.push_back(pair<int, int>(x,y));
    }
    sort(v.begin(), v.end(), cmp);
    int cur_point=v.front().second;
    int num=1;
    for (int i=1; i<v.size(); i++) {
        if(v[i].first>cur_point)
        {
            cur_point=v[i].second;
            num++;
        }
    }
    cout<<num<<endl;
    return 0;
}



【例题——>另一种思路】

【题目描述】

某条街道上有很多个广告位,一个公司在这条街上投放广告,因为不同地方的人流量是不同的,所以公司先做了个调查,共调查了N个人,知道了他们每个人每天在街上走的路段。现在要求找到一些广告位,使得广告位数量最少,但是要求调查到的那些每人至少看到广告K次。如果有人走的路段广告位少于K个,那么要求他在这个路段的所有广告位都要看到。输出要求的广告位的位置。


区间的右端点即可。择区间的右端点即可。


分析: 典型的区间选点问题。


1.先按照区间右端点从小到大的顺序排列,右端点相等,按左端点从大到小的顺序。


2.循环遍历每个区间,把访问过的位置i即放了广告牌的位置用vis【i】设为1


①若区间长度<=K,则区间内的每个位置全部要放广告牌,从区间左端点->右端点挨个遍历,未访问(vis【i】==0)的放置广告牌,计数器cnt++


②若区间长度>K,则区间内只要放置K个广告牌即可,先从左端点->右端点挨个遍历,计算已经放置的广告牌数num,得到的num>=K,则不用再放,继续下一个区间,小于K,则偏向右方的位置优先放置广告牌,即从右端点-->左端点遍历,未访问的放广告牌

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define de 10000
using namespace std;
 
int K,n;      //K表示最少看到的广告牌数,n为人的个数
struct Node
{
    int left,right;
    bool operator<(Node p)        //自定义比较函数
    {
        if(right!=p.right)        //按照区间右端点从小到大的顺序排序,相等按左端点从大到小的顺序排序
            return right<p.right; 
        else return left>p.left;
    }
};
Node p[1005];
int vis[20005];
 
 
void solve()
{
     int i,j,cnt=0,num;
     for(i=0;i<n;i++)
     {
         if((p[i].right-p[i].left+1<=K))          //如果区间长度小于K,则区间内所有数都要放广告牌
         {
             for(j=p[i].left;j<=p[i].right;j++)   //从区间左端点遍历到右端点,未访问过的+1,设为访问过
             {
                 if(vis[j]==0)
                 {
                     vis[j]=1;
                     cnt++;
                 }
             }
         }
         else                                     //区间长度大于K 
         {
             num=0;                             
             for(j=p[i].left;j<=p[i].right;j++)   //先从区间左端点到右端点,计算已经放的广告牌数num
             {
                 if(vis[j]==1)
                    num++;
             }
             if(num<K)                            //num不够规定的K个
             for(j=p[i].right;j>=p[i].left;j--)   //从区间右端点到左端点,没访问的放广告牌,当num==k时跳出
             {
                 if(vis[j]==0)
                 {
                     num++;
                     cnt++;
                     vis[j]=1;
                 }
                 if(num>=K) break;
             }
         }
     }
     cout<<cnt<<endl;
     for(i=0;i<20005;i++)                         
        if(vis[i]==1)
         cout<<i-10000<<endl;                     //注意输出的是i-10000
 
}
 
 
int main()
{
    int i,j,m,left,right;
    cin>>m;
 
    for(i=0;i<m;i++)
    {
        cin>>K>>n;
        for(j=0;j<n;j++)
        {
            cin>>left>>right;
            if(left>right)
            {
                left=left+right;
                right=left-right;
                left=left-right;
            }
            p[j].left=left+de;                 //+10000保证区间内的数都是整数,vis便于访问
            p[j].right=right+de;
        }
        sort(p,p+n);            
        solve();
        memset(vis,0,sizeof(vis));
        if(i!=m-1) cout<<endl;
    }
    return 0;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

最小生成树(1)

最小生成树(1)

一、定义一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。最小生成树可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求出...

深搜剪枝技巧

一、什么是剪枝     首先应当明确的是,“剪枝”的含义是什么。我们知道,搜索的进程可以看作是从树根出发,遍历一棵倒置的树——搜索树的过程。而所谓剪枝,顾名思义...

【题解】均分纸牌

【题目描述】有n堆纸牌,编号分别为 1,2,…, n。每堆上有若干张,但纸牌总数必为n的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为1的堆上取的纸牌,只能移到编号为 2 的堆上;在...

【入门篇】C++ 中变量的简单使用

【入门篇】C++ 中变量的简单使用

1.什么是变量”变量“通俗来讲就是能变的量。在程序设计中,变量是一个个不同类型的盒子,当盒子里装了苹果时,盒子就代表苹果,当然,我们需要给一个个盒子起不同的名字。像下面的图片一样,一个盒子,给他取一个...

【数论】组合数学—容斥原理

【数论】组合数学—容斥原理

概念在计数时,必须注意没有重复,没有遗漏。为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重...

如何判断回文数/回文串

所谓回文,就是从左往右读和从右往左读都是一样的,这样的数字或者字符称为回文数/回文字符。做题的时候经常能看到判断回文操作。判断回文的一般有两种,一种是数字类型,一种是字符类型。两种分别介绍一下。一、回...