目錄

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