求分析复杂度
  • 板块灌水区
  • 楼主Autumn_Rain
  • 当前回复30
  • 已保存回复30
  • 发布时间2024/12/21 11:14
  • 上次更新2024/12/21 21:39:04
查看原帖
求分析复杂度
826079
Autumn_Rain楼主2024/12/21 11:14
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int n,ans,f[N];
struct node{
	int a,b;
}t[N];
bool cmp(node x,node y){
	if(x.a+x.b!=y.a+y.b) return x.a+x.b<y.a+y.b;
	else if(x.a!=y.a) return x.a<y.a;
	else return x.b<y.b;
}
signed main(){
	cin>>n;
    for(int i=1;i<=n;i++){
    	f[i]=1e18;
        cin>>t[i].a>>t[i].b;
    }
    sort(t+1,t+n+1,cmp);
	for(int i=1;i<=n;i++){
		int p=upper_bound(f+1,f+n+1,t[i].a)-f;
		for(int j=p;j>=1;j--){
			f[j]=min(f[j-1]+t[i].b,f[j]);
		}
		ans=max(ans,p);
	}
	cout<<ans;
	return 0;
}
2024/12/21 11:14
加载中...