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