想了好久的策略发现都wa了
后面仔细思考了一下 我们肯定只选一种bi
那我们不妨枚举bi 然后比bi大的ai我们都选
我的写法有点问题 要加特判
其实是可以二分找到大于bi的点 更好写一些
明天吧这个题 和 上一个拓扑的题写一下简单写法
void solve(){
int n,m;cin>>m>>n;
vector<int>a(n+1),b(n+1),A;
int ans=0;
vector<PII>v;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
v.push_back({b[i],a[i]});
A.push_back(a[i]);
}
sort(all(v),greater<>());
sort(all(A));
if(m<=n) {
for (int i = n-1; i >= n-m; i--) {
ans += A[i];
}
}
int now=0,cnt=0;
for(auto [b,a]:v){
while(A.size()&&A.back()>b){
now+=A.back();
A.pop_back();
cnt++;
}
if(a>b){
if(m>=cnt)ans=max(ans,now+(m-cnt)*b);
}else{
if(m>=cnt+1)ans=max(ans,now+a+(m-1-cnt)*b);
}
}
cout<<ans<<endl;
}