[数据结构与算法]22.2.7~2.8

一.算法学习

1.贪心-区间选点；

排序右端点，从左往右选右端点，

如果该区间的右端点小于下个区间的左端点，则要进行选点，选下个区间的右端点；

如果该区间的右端点大于下个区间的左端点，不用选点，比较下下个区间，同理类推；

#include<bits/stdc++.h>
#define rep1(i,a,n) for(int i=a;i<n;i++)
#define rep2(i,a,n) for(int i=a;i<=n;i++)
#define per1(i,n,a)	for(int i=n;i>a;i--)
#define per2(i,n,a) for(int i=n;i>=a;i--)
using ll=long long ;
using namespace std;
const int N = 100010;
int n;
struct Range
{
    int l, r;
}range[N];
bool cmp(Range a,Range b)
{
	return a.r<b.r;
}
int main()
{
    scanf("%d", &n);
    rep1(i,0,n) scanf("%d%d", &range[i].l, &range[i].r);
    sort(range, range + n,cmp);
    int res = 1, ed = range[0].r;先选中第一个右端点，所以res从1开始；
    rep1(i,1,n)
        if (ed < range[i].l)
        {
            res ++ ;
            ed = range[i].r;
        }
    printf("%d\n", res);
    return 0;
}

2.贪心—最大不相交区间数量

?原理同上；就是感觉用到了贪心的一大特性，找不到反例，直接用就行；

我的第一思路就是排序右端点，选中第一个区间的右端点，比较下个区间的左端点，不相交，右端点改变为该区间的右端点，一直往下找；因为有排序，并且从第一个区间开始选的，所以这样找出来一定是最大值；

#include<bits/stdc++.h>
#define rep1(i,a,n) for(int i=a;i<n;i++)
#define rep2(i,a,n) for(int i=a;i<=n;i++)
#define per1(i,n,a)	for(int i=n;i>a;i--)
#define per2(i,n,a) for(int i=n;i>=a;i--)
using ll=long long ;
using namespace std;
const int N=1e5+10;
struct ji{
	int l;
	int r;
}a[N];
bool cmp(ji a,ji b)
{
	return a.r<b.r;
}
int n;
int main()
{	
	cin>>n;
	rep2(i,1,n)
	{
		scanf("%d%d",&a[i].l,&a[i].r);
	}
	sort(a+1,a+n+1,cmp);
	int ans=1,ed=a[1].r;
	rep2(i,2,n){
		if(a[i].l>ed)ans++,ed=a[i].r;
	}
	cout<<ans;
	return 0;		 
}

二.

1.char c[N];

scanf("%s",&c+1)无法完成输入，要么cin>>c+1,要么scanf("%s",&c)；！！！！！

用循环输入也出错！QAQ

以后输入字符串就用上面两种方式就好；记住了！！！！；