选择不相交问题
问题描述：
数轴上有n个开区间（ai，bi），尽量选择多个区间，是的这些区间两两之间没有共同点。
例题
51Nod 1133
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1133
题目分析
将所有的线段按照终点升序，起点降序的顺序进行排列。
贪心策略是：选择第一个线段，之后每次选择不相交的线段，凡是相交或者是覆盖的线段均丢弃。
AC代码
#include <iostream>
#include <algorithm>
using namespace std;
struct line
{
int s;
int e;
} a[100000];
bool cmp(line a, line b)
{
if(a.e == b.e)
{
return a.s > b.s;
}
else return a.e < b.e;
}
int main()
{
int n,s = 1;
cin>>n;
for(int i=0; i<n; i++)
{
cin>>a[i].s>>a[i].e;
}
sort(a,a+n,cmp);
for(int i=1; i<n; i++)
{
if (a[i].e==a[i-1].e || a[i].s<a[i-1].e)
{
a[i]=a[i-1];
}
else
{
s++;
}
}
cout<<s;
return 0;
}
线段重叠问题
问题描述：
多条线段计算最长重复区间
例题：
51Nod 1091
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1091
题目分析
将所有线段按照起点升序，终点降序的顺序进行排列。
贪心策略是：选择第一条线段为m线段，之后的线段终点若是终点在的m线段之前，计算重复距离并与之前计算的最大值比较；之后的线段若是终点在m线段之后，计算重复距离并更新m线段。
AC代码
#include <iostream>
#include <algorithm>
using namespace std;
struct line
{
int s,e;
} a[1000000];
bool cmp(line a, line b)
{
if(a.s == b.s)
{
return a.e > b.e;
}
else return a.s < b.s;
}
int main()
{
int n,s=1;
cin>>n;
for(int i=0; i<n; i++)
cin>>a[i].s>>a[i].e;
sort(a,a+n,cmp);
line m = a[0];
int ans;
for(int i=1; i<n; i++)
{
if(a[i].e<=m.e)
ans=max(ans,a[i].e-a[i].s);
else
{
ans=max(ans, m.e-a[i].s);
m=a[i];
}
}
cout<<ans;
return 0;
}
区间选点问题
问题描述：
数轴上有n个闭区间[ai,bi]。选取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。
例题
NYOJ 891
http://nyoj.top/problem/891
题目分析
将所有线段按照终点升序，起点降序的顺序进行排列。
贪心策略是每次取线段的最后一个点。
AC代码
#include <iostream>
#include <algorithm>
using namespace std;
struct line
{
int s,e;
} a[10000];
bool cmp(line a, line b)
{
if(a.e == b.e)
{
return a.s > b.s;
}
else return a.e < b.e;
}
int main()
{
int n;
while(cin>>n)
{
for(int i=0; i<n; i++)
{
cin>>a[i].s>>a[i].e;
}
sort(a,a+n,cmp);
int ans = 1;
int point = a[0].e;
for(int i=1; i<n; i++)
{
if(a[i].s > point)
{
point = a[i].e;
ans++;
}
}
cout<<ans<<endl;
}
return 0;
}
区间覆盖问题
区间完全覆盖问题
问题描述：
给定一个长度为m的区间，再给出n条线段的起点和终点（注意这里是闭区间），求最少使用多少条线段可以将整个区间完全覆盖。
例题
POJ 1089
http://poj.org/problem?id=1089
问题分析
将所有线段按照起点升序，终点升序的顺序进行排列。
排列后的线段，首先选取第一个线段，接下来凡是起点在第一个线段终点之前的线段都是我们的备选线段，我们需要选择的是终点最大的线段，依次类推。
AC代码
区间部分覆盖问题
问题描述：
数轴上有n个闭区间[ai,bi]，选择尽量少的区间覆盖一条指定线段[s,t]。
问题分析
将所有线段按照起点升序，终点降序的顺序排列，并且将所有在区间之外的部分切割掉。
贪心策略是每次选择最长的线段，然后改变区间的左端点为选择线段的右端点，重复上述过程。
经典的几道区间相关问题
喷水装置
AC代码
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int cmp(double a, double b)
{
return a>b;
}
int main()
{
int n;
double a[1000];
cin>>n;
while(n--)
{
int num;
cin>>num;
for(int i=0;i<num;i++)
{
cin>>a[i];
a[i] = sqrt(a[i]*a[i] - 1)*2;
}
sort(a,a+num,cmp);
int ans = 0;
int count = 0;
double len = 20;
while(len>0)
{
len = len - a[count];
count++;
ans++;
}
cout<<ans<<endl;
}
}
喷水装置2
解题思路
思路类似于完全区间覆盖，只需计算出每个喷水装置的喷水起点和终点就好了。
AC代码
网友评论