区间贪心问题整理

学了也七八个月了,虽然确实刷了一些题,但是实力依旧如此lj,一些当时写过的题目没有好好整理,有非常多经典的题目都没有深入下去,怎么提高呢?

Problem 905. 区间选点

刷 112. 雷达设备 要用到区间选点的贪心策略,当时记得基础课那几道关于区间问题的贪心策略大部分都是以右端点进行排序,学的时候也不太明白为什么不用左端点进行排序,时隔七、八个月再写的时候，发现一道模板题都不太清楚了,真实该挨揍了

$用左端点排序写的，后来分析的时候很明显有反例,2/10(只能过两个测试点)$

反例	
3
1 4
2 6
3 5 此时答案是2

/*Love coding and thinking!*/ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo2(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
const int N=2e5+10;
int n,m,_,x;
int a[N],c[N];
int res=1,aver;

struct node
{
	int l,r;
}Node[N];

bool cmp(node a,node b)
{
	return a.l<b.l;
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%d%d",&Node[i].l,&Node[i].r);
	
	sort(Node+1,Node+1+n,cmp);//默认用左端点
	int last=Node[1].r;
	
	for(int i=2;i<=n;i++)
	{
		if(Node[i].l>Node[i-1].r)
			res++,last=max(last,Node[i].r);
		else
		{
			last=max(last,Node[i].r);
		}
	}
	cout<<res;
	return 0;
}

$后来针对上边这种情况瞎改的,emmm,一言难尽,明显n=1,输出0$

/*Love coding and thinking!*/ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo2(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
typedef pair<int,int>PII;
typedef pair<long,long>PLL;


typedef long long ll;
const int N=2e5+10;
int n,m,_,x;
int a[N],c[N];
int res=1,aver;

struct node
{
	int l,r;
}Node[N];

bool cmp(node a,node b)
{
	return a.l<b.l;
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%d%d",&Node[i].l,&Node[i].r);
	
	sort(Node+1,Node+1+n,cmp);//默认用左端点
	int last=Node[1].r;s
	
	for(int i=2;i<=n;i++)
	{   
		if(Node[i].l>Node[i-1].r)
			res++,last=max(last,Node[i].r);
		else
		{
			res++;
			last=Node[i].r;
		}
	}
	cout<<res-1;
	return 0;
}

$sort右端点发现还是有问题,人没了$

/*Love coding and thinking!*/ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo2(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
typedef pair<int,int>PII;
typedef pair<long,long>PLL;
typedef long long ll;
const int N=2e5+10;

struct node
{
	int l,r;
}Node[N];

bool cmp(node a,node b)
{
	return a.r<b.r;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%d%d",&Node[i].l,&Node[i].r);
	
	sort(Node+1,Node+1+n,cmp);//默认用左端点
	
	int last=Node[1].r;
	
	for(int i=2;i<=n;i++)
	{
		if(Node[i].l>last)
			res++,last=Node[i].r;
		else
		{
			last=Node[i-1].r;
		}
	}
	cout<<res;
	return 0;
}

我是傻子

/*Love coding and thinking!*/ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo2(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
typedef pair<int,int>PII;
typedef pair<long,long>PLL;
typedef long long ll;
const int N=2e5+10;

struct node
{
	int l,r;
}Node[N];
int res=1,n;
bool cmp(node a,node b)
{
	return a.r<b.r;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%d%d",&Node[i].l,&Node[i].r);
	
	sort(Node+1,Node+1+n,cmp);//默认用左端点
	//贪心策略，如果第i个区间的l>上一个区间的右端点，答案++
    //否则右端点更新.
	int last=Node[1].r;
	
	for(int i=2;i<=n;i++)
	{
		if(Node[i].l>last)
			res++,last=Node[i].r;
	}
	cout<<res;
	return 0;
}

雷达设备

/*Love coding and thinking!*/ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo2(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
typedef pair<int,int>PII;
typedef pair<long,long>PLL;
typedef long long ll;
const int N=2e5+10;

struct node
{
	int l,r;
}Node[N];

int cnt=0;
struct seg
{
	double l,r;
}Seg[N];

bool cmp(seg a,seg b)
{
	return a.r<b.r;
}

int res=1,n,D;


int main()
{
	cin>>n>>D;
	for(int i=1;i<=n;i++)
		scanf("%d%d",&Node[i].l,&Node[i].r);
	
	for(int i=1;i<=n;i++)
	{
		if(Node[i].r>D)
		{
			cout<<"-1";
			return 0;		
		}
		else
		{
			double d=sqrt(D*D-Node[i].r*Node[i].r);
			Seg[cnt].l=Node[i].l-d;
			Seg[cnt++].r=Node[i].l+d;
		}
	}	
	
	sort(Seg,Seg+cnt,cmp);//默认用左端点
	
	// for(int i=0;i<cnt;i++)
	// {
		// cout<<Seg[i].l<<" "<<Seg[i].r<<endl;
	// }
	
	//贪心策略，如果第i个区间的l>上一个区间的右端点，答案++
    //否则右端点更新.
	double last=Seg[0].r;
	
	for(int i=1;i<cnt;i++)
	{
		if(Seg[i].l>last)
			res++,last=Seg[i].r;
	}
	cout<<res;
	return 0;
}