本文主要是介绍贪心（不相交的开区间、区间选点、带前导的拼接最小数问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
1.简单贪心
2.区间贪心
不相交的开区间
1.如何删除？
2.如何比较大小
区间选点问题
3.拼接最小数
1.简单贪心
比如：给你一堆数，你来构成最大的几位数
2.区间贪心
不相交的开区间
思路：
首先，如果有两个区间包含关系，肯定是取小的那个，扔掉大的那个。
上一步操作完了之后，区间就互不包含，于是，每次都在保证不相交的前提下，
取左端点最大的（或每次都取右端点最小的）
思路是这样没错，实现遇到的问题：
1.如何删除？
看了参考代码，不用删除，因为如果取左端点最大的，必定是被包含的那个区间，第二部包含了第一步，“首先”可以不干。
2.如何比较大小
需要回忆之前学的“排序”，构造结构体，构造cmp函数
通过代码
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=10002;
int n=2,W=2;
int l[N]={1,2},r[N]={5,6};int ans=0;
struct qj
{int left;int right;
}I[N];
bool cmp(qj a1,qj a2)
{if(a1.left!=a2.left) return a1.left>a2.left;else return a1.right<a2.right;
}int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++){scanf("%d %d",&I[i].left,&I[i].right);}
sort(I,I+n,cmp);
if(n>0) ans++;
int l1=I[0].left;
for(int i=1;i<n;i++)
{if(I[i].right<=l1){ans++;l1=I[i].left;}
}
printf("%d",ans);
}区间选点问题
其实就是：不相交的闭区间
点=列举出的所有不相交的闭区间的左端点
真的只改了一个小于号
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=10002;
int n=2,W=2;
int l[N]={1,2},r[N]={5,6};int ans=0;
struct qj
{int left;int right;
}I[N];
bool cmp(qj a1,qj a2)
{if(a1.left!=a2.left) return a1.left>a2.left;else return a1.right<a2.right;
}int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++){scanf("%d %d",&I[i].left,&I[i].right);}
sort(I,I+n,cmp);
if(n>0) ans++;
int l1=I[0].left;
for(int i=1;i<n;i++)
{if(I[i].right<l1){ans++;l1=I[i].left;}
}
printf("%d",ans);
}3.拼接最小数
仔细看例子
思路
问题：如何接收这些输入？并转化为实体？
不能以%d输入，会丢失信息
答案使用了string类（c++类别），使用cincout
string数组，每一个元素都是string
答案使用了自己构造cmp
if a+b<b+a,则a排b前，让sort自己排序
输出要注意00 000的情况，输出且只输出一个0
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=10002;
int n;
string str[N];
bool cmp(string a,string b)
{return a+b<b+a;
}
int main()
{
// string a="123";
// cout<<(a[0]=="1");//"1"报错，'1'true，1false cin>>n;int flag=0;for(int i=0;i<n;i++)cin>>str[i];sort(str,str+n,cmp);for(int j=0;j<n;j++)
{for(int i=0;i<str[j].length();i++) { if(str[j][i]!='0') flag=1;if(flag) cout<<str[j][i];}}
if(!flag) cout<<0;
}答案是这样的，从while开始看，用了高端的begin与erase
bool cmp(string a, string b) {return a + b < b + a;
}int main() {int n;cin >> n;for (int i = 0; i < n; i++) {cin >> nums[i];}sort(nums, nums + n, cmp);string result = "";for (int i = 0; i < n; i++) {result += nums[i];}while (result.length() > 1 && result[0] == '0') {result.erase(result.begin());}cout << result << endl;return 0;
}这篇关于贪心（不相交的开区间、区间选点、带前导的拼接最小数问题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
