算法提高 线段和点
时间限制：1.0s 内存限制：256.0MB
问题描述
有n个点和m个区间，点和区间的端点全部是整数，对于点a和区间[b,c]，若a>=b且a<=c，称点a满足区间[b,c]。
求最小的点的子集，使得所有区间都被满足。
输入格式
第一行两个整数n m
以下n行 每行一个整数，代表点的坐标
以下m行 每行两个整数，代表区间的范围
输出格式
输出一行，最少的满足所有区间的点数，如无解输出-1。
样例输入
5 5
2
6
3
8
7
2 5
3 4
3 3
2 7
6 9
样例输出
2
数据规模和约定
1<=n,m<=10000
0<=点和区间的坐标<=50000
#include<stdio.h>
int N=5,M=5;
int spot[10001]={0,2,6,3,8,7};
int sec[10001][2]={
{0},
{2,5},
{3,4},
{3,3},
{2,7},
{6,9},
};
int isSec[10001];
int isSpot[50001];
void sort(){
int i,j;
int tempB,tempE;
for(i=1;i<=M;i++){
for(j=1;j<=M-i;j++){
if(sec[j][0]>sec[j+1][0]||(sec[j][0]==sec[j+1][0]&&sec[j][1]>sec[j+1][1])){
tempB=sec[j][0]; tempE=sec[j][1];
sec[j][0]=sec[j+1][0]; sec[j][1]=sec[j+1][1];
sec[j+1][0]=tempB; sec[j+1][1]=tempE;
}
}
}
}
void cometrue(){
int i=0;
for(i=1;i<=N;i++)
isSpot[spot[i]]=1;
}
int fun(){
int count=0,tempNum,cur,tag=0;
int i,j,k;
sort(); cometrue();
/* for(i=1;i<=M;i++){
printf("s:%d e:%d\n",sec[i][0],sec[i][1]);
} */
for(i=1;i<=M;i++){
tempNum=-1; tag=-1;
if(isSec[i]!=1){
for(j=sec[i][0];j<=sec[i][1];j++){
if(isSpot[j]==1){
cur=-1;
for(k=i+1;k<=M;k++){
if(sec[k][0]<=j&&j<=sec[k][1]&&!isSec[k])
cur++;
else break;
}
if(tempNum<cur) {tempNum=cur; tag=j;}
}
}
++count;
for(k=i;k<=M;k++)
if(sec[k][0]<=tag) isSec[k]=1;
else break;
}
}
if(count==0) return -1;
return count;
}
int main()
{
int i=0;
scanf("%d%d",&N,&M);
for(i=1;i<=N;i++) scanf("%d",&spot[i]);
for(i=1;i<=M;i++) scanf("%d%d",&sec[i][0],&sec[i][1]); /* */
printf("%d\n",fun());
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-17640.html
