GESP4级考试语法知识（贪心算法（四））

整数区间1代码：

#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct node
{
int l,r;
}a[1001];
bool cmp(node a,node b)
{
return a.r<b.r;
};
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i].l>>a[i].r;
}
sort(a,a+n,cmp);
int temp=0,ans=1;
for(int i=1;i<n;i++)
{
if(a[temp].r>=a[i].l) continue ;
else
{
temp=i;
ans++;
}
}
cout<<ans<<endl;
 return 0;
}

整数区间2代码：

#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
int x,y,s;
bool operator < (const node &p)const
{
if(y<p.y) return 1;
else if(y==p.y&&x<=p.x) return 1;
return 0;
}
} a[10005],t;
int main()
{
int n,i,j,sum=0;
scanf("%d",&n);
for(i=1; i<=n; i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
a[i].s=2;//标记该闭区间剩下需要的元素
}
sort(a+1,a+n+1);//排序
for(i=1; i<=n; i++)
{
if(a[i].s>0)   //a[i]可用
{
a[i].s--;//a[i]所需的元素-1
for(j=i+1; j<=n; j++)   //该元素在其他闭区间是否存在
{
if(a[i].y>=a[j].x&&a[i].y<=a[j].y)
a[j].s--;
}
sum++;
if(a[i].s>0)   //再进行一次判断
{
a[i].s--;
for(j=i; j<=n; j++)
{
if(a[i].y-1>=a[j].x&&a[i].y-1<=a[j].y)
a[j].s--;
}
sum++;
}
}
}
printf("%d",sum);
}

原文地址：https://blog.csdn.net/weixin_60445850/article/details/143759669

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！