点击打开链接uva 10200
题目意思: 给定一个值m作为区间的右端点,区间的左端点为0,现在给定一些小区间,要求找到最少的区间数完全覆盖区间[0,m]
解题思路: 1:第一种区间覆盖问题,求解完全覆盖区间所需最小的区间数
2:(1)区间完全覆盖问题
问题描述:给定一个长度为m的区间,再给出n条线段的起点和终点(注意这里是闭区间),求最少使用多少条线段可以将整个区间完全覆盖
样例:
区间长度8,可选的覆盖线段[2,6],[1,4],[3,6],[3,7],[6,8],[2,4],[3,5]
解题过程:
1将每一个区间按照左端点递增顺序排列,拍完序后为[1,4],[2,4],[2,6],[3,5],[3,6],[3,7],[6,8]
2设置一个变量表示已经覆盖到的区域。再剩下的线段中找出所有左端点小于等于当前已经覆盖到的区域的右端点的线段中,右端点最大的线段在加入,直到已经覆盖全部的区域
3过程: 假设第一步加入[1,4],那么下一步能够选择的有[2,6],[3,5],[3,6],[3,7],由于7最大,所以下一步选择[3,7],最后一步只能选择[6,8],这个时候刚好达到了8退出,所选区间为3
4贪心证明: 需要最少的线段进行覆盖,那么选取的线段必然要尽量长,而已经覆盖到的区域之前的地方已经无所谓了,(可以理解成所有的可以覆盖的左端点都是已经覆盖到的地方),那么真正能够使得线段更成的是右端点,左端点没有太大的意义,所以选择右端点来覆盖
3:就是运用sort,和结构体的排序,以及路径的保存
代码:
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
#define MAXN 100010
int t , m , len , ans;
struct node{
int l;
int r;
friend bool operator<(node a , node b){//重载小于号
if(a.l < b.l)
return true;
if(a.l == b.l && a.r < b.r)
return true;
return false;
}
}s[MAXN] , path[MAXN];
void solve(){
int i , j , left , max , flag , pos;
sort(s , s+len);
left = 0 ;
ans = 0;
j = 0;
while(1){
if(left >= m)
break;
max = 0 ;
flag = 0;
for(i = 0 ; i < len ; i++){
if(s[i].l <= left){
if(max < s[i].r){
max = s[i].r;
pos = i;
flag = 1;
}
}
}
if(flag){
ans++;
path[j++] = s[pos];//记录路径
left = max;
}
else
break;
}
if(flag){
printf("%d\n" , ans);
for(i = 0 ; i < j ; i++)
printf("%d %d\n" , path[i].l , path[i].r);
}
else
printf("0\n");
}
int main(){
//freopen("input.txt" , "r" , stdin);
int i , a, b;
scanf("%d%*c" , &t);
while(t--){
scanf("%d" , &m);
for(i = 0 ; ; i++){
scanf("%d%d" , &a , &b);
if(!a && !b)
break;
s[i].l = a;
s[i].r = b;
}
len = i;
solve();
if(t)
printf("\n");
}
return 0;
}
分享到:
相关推荐
CentOS-7-x86_64-Minimal-1810.iso镜像文件
CentOS-7-x86_64-Minimal-1908
CentOS是免费的、开源的、可以重新分发的开源操作系统,CentOS(Community Enterprise Operating System,中文意思是社区企业操作系统)是Linux发行版之一。...CentOS-7-aarch64-Minimal-2009适用于ARM64 (aarch64)
CentOS-7-x86-64-Minimal-2207-02.iso
CentOS-7-x86_64-Minimal-1908,官方下载版
CentOS-6.10-x86_64-minimal.iso
tez-0.10.1-SNAPSHOT-minimal.tar.gz
CentOS 7.9版本(CentOS-Userland-7-armv7hl-RaspberryPI-Minimal-4-2009-sda.raw.xz)适用于ARM32 (armhfp) CentOS是免费的、开源的、可以重新分发的开源操作系统,CentOS(Community Enterprise Operating System...
CentOS 7.9版本(CentOS-Userland-7-armv7hl-generic-Minimal-2009-sda.raw.xz)适用于ARM32 (armhfp) CentOS是免费的、开源的、可以重新分发的开源操作系统,CentOS(Community Enterprise Operating System,中文...
Better-Minimal-WebGL-Template unity webgl打包模板 支持手机
centos7纯净版(约700M)CentOS-7-x86_64-Minimal-1708.iso 资源是一个文本文件,内容是一个百度云盘链接 怕链接失效而导致客观不满意,我先把链接贴出来 如果还能打开,那就下载后查看密码吧,不能就不好意思了 ...
iso镜像文件CentOS7最小化安装CentOS-7-x86_64-Minimal-1611,初学者必备
CentOS7 mini版
linux centos7 64位 命令行界面
centos7
放置在具有同名文件的目录下,替换掉原来的同名文件。使用文件查找工具查找同名文件并替换。参考路径:Program Files\Adobe\Adobe After Effects CC 2018\Support Files
kubespherev2.1的最小化安装文件,可以对应kubernetesv1.17.3版本安装。
mysql-8.0.17-linux-x86_64-minimal.tar.xz安装包用于自定义安装MySQL,相比yum安装MySQL它能够按照您的需求定制化的安装MySQL。源码配置安装MySQL更加有利于我们学习使用MySQL。
CentOS-6.5-i386-minimalCentOS-6.5-i386-minimalCentOS-6.5-i386-minimal