【题目描述】
有一条很长的尺子,上面标记着整数点的坐标。如:
现在给出n条线段,每条线段表示为x—y(x和y为整数,x<=y),两条线段能合并的条件是x—y,y—z,合并为x—z。比如线段2—4和线段4—6可以合并为线段2—6。(线段2—4和线段3—6则不可以合并为线段2—6)
求最终能合并的最长的线段,且输出这条最长的线段是由多少条小线段组成的。
比如有6条线段:2—7,1—3,3—12,12—20,7—10,4—50
那么可以合并成以下线段:
1—3,3—12,12—20 长度为20-1=19 由3个线段组成
2—7,7—10 长度为10-2=8 由2个线段组成
4—50 长度为50-4=46 由1个线段组成
那么最长的一条就是第三个,所以结果为46,1。
需要注意的是:如果有两条不一样的连续的线段长度同时为最大,那么取组成线段数多的一条。
例子:1—5,5—10,1—10,输出: 9,2
【输入文件】
第一行为一个整数n;
第二行到第n+1行,每行两个整数A B,记录一条线段的信息。
【输出文件】
输出一个整数,即能合并成的最长的线段的长度和组成它的线段数。
【输入输出样例1】
7
1 5
10 12
3 10
2 7
2 10
12 16
7 9 14 3
【样例1数据提示】
1—5 长度为4 由1个页段组成
3—10,10—12,12—16 长度为13 由3个页段组成
2—7,7—9 长度为7 由2个页段组成
2—10,10—12,12—16 长度为14 由3个页段组成
所以输出最长的页段的长度即14由3个页段组成
【数据规模】
对于30%的数据:1<=n<=20;对于100%的数据:1<=n<=500 ,0<=A<B<500
其实这道题有点DP的意思了
先进行排序,y来排序。
我们先定义一个s数组,s[i]表示以线段i结尾的能合并的线段最长为多长
定义c数组,c[i]表示以线段i结尾的能合并的线段最长的最多要多少条线段
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
int x,y;
}a[510];
bool cmp(node x,node y){return x.y<y.y;}
int n,s[510],c[510];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d%d",&a[i].x,&a[i].y);//输入
sort(a+1,a+n+1,cmp);//排序
for(int i=1;i<=n;++i)
{
s[i]=a[i].y-a[i].x;//初始化,s[i]最长为线段i的长度
c[i]=1;//有一条线段,为线段i
for(int j=i-1;j>=1;--j)
if(a[j].y==a[i].x)
//如果线段i的头部(x)能和线段j的尾部(y)连接的话
{
if(s[i]<s[j]+a[i].y-a[i].x)//判断是否能更新长度
{
//能更新
s[i]=s[j]+a[i].y-a[i].x;
c[i]=c[j]+1;//更新长度
}
//若不能更新长度
else if(s[i]==s[j]+a[i].y-a[i].x)
//判断是否长度相等
{
if(c[i]<c[j]+1)c[i]=c[j]+1;
//可以就更新
}
}
}
int maxa=0,maxb=0;
//maxa求最长的长度,maxb求合并的线段最长的最多要多少条线段
for(int i=1;i<=n;++i)//更新,不多说
{
if(s[i]>maxa)
{
maxa=s[i];maxb=c[i];
}
else if(s[i]==maxa)
{
if(maxb<c[i])maxb=c[i];
}
}
printf("%d %d\n",maxa,maxb);//输出,完结撒花
return 0;
}
纯代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
int x,y;
}a[510];
bool cmp(node x,node y){return x.y<y.y;}
int n,s[510],c[510];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d%d",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;++i)
{
s[i]=a[i].y-a[i].x;
c[i]=1;
for(int j=i-1;j>=1;--j)
if(a[j].y==a[i].x)
{
if(s[i]<s[j]+a[i].y-a[i].x)
{
s[i]=s[j]+a[i].y-a[i].x;
c[i]=c[j]+1;
}
else if(s[i]==s[j]+a[i].y-a[i].x)
{
if(c[i]<c[j]+1)c[i]=c[j]+1;
}
}
}
int maxa=0,maxb=0;
for(int i=1;i<=n;++i)
{
if(s[i]>maxa)
{
maxa=s[i];maxb=c[i];
}
else if(s[i]==maxa)
{
if(maxb<c[i])maxb=c[i];
}
}
printf("%d %d\n",maxa,maxb);
return 0;
}