题意:有n个任务,每一天可以选择一个未完成的任务i来完成,并在ai天后获得bi的利益。问在m天内最多可以获得多少利益。
首先我们可以考虑假如i,j两个任务都在我们最后的答案里面,那么让a比较大的排在前面一定是更好的。所以我们先按照a降序排序。
然后用一个set维护前面已经选了的任务
新加一个任务就分为两种情况
设size为set的大小
如果size+a[i]<=m则直接加入,否则看set的最小值,如果当前最小值小于bi则进行替换,因为新加入的ai比前面的aj小,所以一定能够替换。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#include<cmath>
#include<set>
#include<unordered_map>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("Yes")
#define B puts("No")
using namespace std;
typedef double db;
typedef long long ll;
//typedef __int128 i128;
const int N=3e5+10;
//const int inf=1ll<<60;
const ll inf=1ll<<60;
const ll mo=1e9+7;
struct node{
ll a,b;
};
node c[N];
multiset<ll> s;
ll n,m,ans;
int main()
{
// freopen("data.in","r",stdin);
scanf("%lld %lld",&n,&m);
fo(i,1,n) scanf("%lld %lld",&c[i].a, &c[i].b);
sort(c+1,c+n+1, [](node a,node b){
return a.a>b.a;
});
fo(i,1,n) {
if ((int)s.size()+c[i].a<=m) {
s.insert(c[i].b);
ans+=c[i].b;
}
else {
if (!s.empty()) {
if (*s.begin()<=c[i].b) {
auto it=s.begin();
ans-=*it;
s.erase(it);
s.insert(c[i].b);
ans+=c[i].b;
}
}
}
}
printf("%lld",ans);
return 0;
}
标签:size,Summer,lld,int,Vacation,include,define
From: https://www.cnblogs.com/ganking/p/17974201