摘要:本文主要向大家介绍了 C/C++知识点之【贪心算法】关于贪心的一些思考,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。
本文主要向大家介绍了 C/C++知识点之【贪心算法】关于贪心的一些思考,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。
贪心最主要的问题就是无后效性
当前最优解就是全局最优解
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct act{
int start;
int end;
}a[105];
int cmp(act a,act b){
return a.end<b.end;
}
int main(){
int n;
while(~scanf("%d",&n)){
for(int i=1;i<=n;i++){
cin>>a[i].start>>a[i].end;
}
//printf("\n");
sort(a+1,a+n+1,cmp);
//for(int i=1;i<=n;i++){
// printf("%d %d\n",a[i].start,a[i].end);
//}
int i=1,sum=1;
for(int j=2;j<=n;j++){
if(a[j].start>=a[i].end){
sum++;
i=j;
}
}
printf("%d\n",sum);
}
return 0;
}
本文由职坐标整理并发布,希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号