Link

Code

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
struct NODE {int p,c;} ;
bool cmp(NODE a,NODE b) {return a.c<b.c;} ;
ll n,k,m,ans,pay ;
short int vis[50004] ;
NODE a[50004] ;
priority_queue<int> q1 ;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q2,q3 ;
int main() {
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) ;
	cin>>n>>k>>m ;
	for(int i=1;i<=n;++i)
		cin>>a[i].p>>a[i].c ;
	sort(a+1,a+n+1,cmp) ;
	for(int i=1;i<=k;++i) {
		pay+=a[i].c ;
		if(pay>m) {
			cout<<i-1 ;
			return 0 ;
		}
		q1.push(a[i].p-a[i].c) ;
	}
	if(k==n) {
		cout<<k ;
		return 0 ;
	}
	ans=k ;
	for(int i=k+1;i<=n;++i) {
		q2.push(make_pair(a[i].c,i)) ;
		q3.push(make_pair(a[i].p,i)) ;
	}
	for(int i=k+1;i<=n;++i) {
		while(vis[q2.top().second])q2.pop() ;
		while(vis[q3.top().second])q3.pop() ;
		int tmp1=q2.top().first+q1.top(),tmp2=q3.top().first ;
		int p1=q2.top().second,p2=q3.top().second ;
		if(tmp1<tmp2) {
			pay+=tmp1 ;
			q1.pop();q2.pop();
			q1.push(a[p1].p-a[p1].c);
			vis[p1]=1;
		}else {
			pay+=tmp2 ;
			q3.pop() ;
			vis[p2]=1 ;
		}
		++ans ;
		if(pay>m) {
			cout<<ans-1 ;
			return 0 ;
		}
	}
	cout<<n ;
	return 0 ;
}

反悔贪心好像被hack了

我有一个朋友说可以二分dp 但是我不知道怎么dp 球思路/转移方程

玄关QAQ