P1 活动安排

# include<iostream>
# include<cstdio>
# include<algorithm>
using namespace std;

struct ts{
	int s,f;
	void in(){
		cin>>s>>f;
	}
}a[1005];

int n,ans=0,m;

bool cmp(ts x,ts y){
	return x.f<y.f;
}

int main(){
	cin>>n;
	for(int i=0;i<n;++i) a[i].in();
	sort(a,a+n,cmp);
	for(int i=0;i<n;++i){
		if(a[i].s>=m){
			++ans;
			m=a[i].f;
		}
	}
	cout<<ans;
	return 0;
}

P2 种树

# include<iostream>
# include<cstdio>
# include<algorithm>
using namespace std;

const int H=5005,N=3e4+5;;

struct ts{
	int s,f,n;
	void in(){
		cin>>s>>f>>n;
	}
	void out(){
		cout<<s<<" "<<f<<" "<<n<<endl;
	}
}a[H];

int n,h,ans=0;
bool v[N];

bool cmp(ts p,ts q){
	return p.f!=q.f?p.f<q.f:p.n>q.n;
}

int main(){
	cin>>n>>h;
	for(int i=0;i<h;++i) a[i].in();
	sort(a,a+h,cmp);
	for(int i=0;i<h;++i){
		int s=a[i].s,f=a[i].f,w=a[i].n,p=0;
		for(int j=s;j<=f;++j)
			if(v[j]) ++p;
		if(p<w){
			p=w-p;
			for(int j=f;p>0;--j){
				if(!v[j]){
					v[j]=1;
					++ans;
					--p;
				}
			}
		}
	}
	cout<<ans;
	return 0;
}

P5 智力大冲浪

# include<iostream>
# include<algorithm>
using namespace std;

const int M=505;

struct ts{
	int t,v;
}a[M];

int m,n;
bool v[M],f;

bool cmp(ts x,ts y){
	return x.v>y.v;
}

int main(){
	cin>>m>>n;
	for(int i=0;i<n;++i) cin>>a[i].t;
	for(int i=0;i<n;++i) cin>>a[i].v;
	sort(a,a+n,cmp);
	for(int i=0;i<n;++i){
		f=1;
		for(int j=a[i].t;j>0;--j)
			if(!v[j]){
				v[j]=1;
				f=0;
				break;
			}
		if(f) m-=a[i].v;
	}
	cout<<m;
	return 0;
}

P6 数列极差

# include<iostream>
# include<cstdio>
# include<algorithm>
# include<queue>
using namespace std;

int n,a[50005],ma,mi;
priority_queue<int,vector<int>,greater<int> > q;

int main(){
	cin>>n;
	for(int i=0;i<n;++i){
		cin>>a[i];
		q.push(a[i]);
	}
	sort(a,a+n);
	mi=a[n-1];
	for(int i=n-2;i>=0;--i) mi=a[i]*mi+1;
	for(int i=1;i<n;++i){
		int x=q.top();
		q.pop();
		int y=q.top();
		q.pop();
		q.push(x*y+1);
	}
	ma=q.top();
	cout<<ma-mi;
	return 0;
}

P7 数列分段

# include<iostream>
# include<cstdio>
# include<algorithm>
# include<queue>
using namespace std;

const int M=1e5+5;
int n,m,a[M],ans=1,s=0;

int main(){
	cin>>n>>m;
	for(int i=0;i<n;++i) cin>>a[i];
	for(int i=0;i<n;++i){
		s+=a[i];
		if(s>m){
			s=a[i];
			++ans;
		}
	}
	cout<<ans;
	return 0;
}

P8 线段

# include<iostream>
# include<cstdio>
# include<algorithm>
using namespace std;

const int M=1e6+5;

struct ts{
	int s,f;
	void in(){
		cin>>s>>f;
	}
}a[M];

int n,ans=0,m;

bool cmp(ts x,ts y){
	return x.f<y.f;
}

int main(){
	cin>>n;
	for(int i=0;i<n;++i) a[i].in();
	sort(a,a+n,cmp);
	for(int i=0;i<n;++i){
		if(a[i].s>=m){
			++ans;
			m=a[i].f;
		}
	}
	cout<<ans;
	return 0;
}

P9 家庭作业

# include<iostream>
# include<queue>
# include<map>
# include<algorithm>
# include<vector>
using namespace std;
# define p pair<int,int>
# define m(a,b) make_pair(a,b)

const int N=1e6+5;

struct ts{
	int t,s;
	void in(){
		cin>>t>>s;
	}
}a[N];

int n,sum=0;
priority_queue<p,vector<p>,greater<p> > q;

bool cmp(ts x,ts y){
	return x.t<y.t;
}

int main(){
	cin>>n;
	for(int i=0;i<n;++i) a[i].in();
	sort(a,a+n,cmp);
	for(int i=0;i<n;++i){
		int t=a[i].t,s=a[i].s;
		q.push(m(s,t));
		if(q.size()>t){
			p v=q.top();
			q.pop();
			sum-=v.first;
		}
		sum+=s;
	}
	cout<<sum;
	return 0;
}