贪心练习题

[USACO 2009 Dec S]Selfish Grazing

代码：

#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 50010
struct node{
	int s;
	int e;
}f[MAXN];
bool cmp(node a,node b){
	return a.s<b.s;
}
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>f[i].s>>f[i].e;
	}
	sort(f,f+n,cmp);
	int maxx=0,ans=0,t;
	for(int i=0;i<n;i++){
		ans=1,t=i; 
		for(int j=i+1;j<n;j++){
			if(f[j].s>=f[t].e){
				ans++;
				t=j;
			}
		}
		maxx=max(maxx,ans);
	}
	cout<<maxx<<endl;
	return 0;
} 
           

[USACO 2006 Ope B]Cows on a Leash

代码：

#include<bits/stdc++.h>
using namespace std;
#define MAXN 32010
pair<int,int>p[MAXN];
int main(){
	int n;
	cin>>n;
	int a,b;
	for(int i=0;i<n;i++){
		cin>>a>>b;
		p[i].second=a;
		p[i].first=a+b;//结束的时间 
	}
	sort(p,p+n);
	int ans=0,temp=0;
	for(int i=0;i<n;i++){
		if(p[i].second>=temp){
			ans++;
			temp=p[i].first;
		}
	}
	cout<<ans<<endl;
	return 0;
}
           

#include<bits/stdc++.h>
using namespace std;
#define MAXN 32010
struct node{
	int l;
	int r;
}f[MAXN];
bool cmp(node x,node y){
	if(x.r==y.r){
		return x.l<y.l;
	}
	return x.r<y.r;
}
int main(){
	int n;
	cin>>n;
	int a,b;
	for(int i=0;i<n;i++){
		cin>>a>>b;
		f[i].l=a;
		f[i].r=a+b;
	}
	sort(f,f+n,cmp);
/*	for(int i=0;i<n;i++){
		cout<<f[i].l<<" "<<f[i].r<<endl;
	}*/
	int ans=0,temp=0;
	for(int i=0;i<n;i++){
		if(f[i].l>=temp){
			ans++;
			temp=f[i].r;
			//cout<<f[i].l<<"*"<<f[i].r<<endl;
		}
	}
	cout<<ans<<endl;
	return 0;
}