贪心（不相交的开区间、区间选点、带前导的拼接最小数问题）

目录

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;
}