题目链接（正睿）
题目大意
给出$n$个活动和每个活动的吸引力和开始和结束时间，总天数为$D$。规定一天最多参加$k$个活动，求哪一天的吸引力总和最大。
$1\le n \le 3 \times 10^5,~1 \le D \le 3\times 10^5$
分析
将所有开始、结束的时间标记一下，使用$\text{set}$动态维护每个时间点吸引力前$k$大的和。具体地，记录每一个时间点第$k$大的数$knum$是多少，如果现在要插入的数比$knum$大，那么插入该数字，$knum$左移一位，否则不用管$knum$，最后维护一下前缀和即可。删除数字是把这个过程逆过来即可。
实现
主要部分就是动态维护$\text{set}$的过程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| while(!a[i].empty()){
ll cur=a[i].front();a[i].pop();
q.insert(cur);
if(q.size()<=k) itk=q.end(),itk--,sum+=cur;
else if(cur>*itk) sum-=*itk,itk--,sum+=cur;
}
maxn=max(maxn,sum);
while(!b[i].empty()){
ll cur=b[i].front();b[i].pop();
auto p=q.find(cur);
if(q.size()<=k) sum-=cur;
else if(cur>=*itk) itk++,sum-=cur,sum+=*itk;
q.erase(p);
}
|
附完整代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=300005;
ll h,s,e,maxn,n,t,d,k,sum;
multiset<ll, greater<ll> > q;
queue<ll> a[N],b[N];
int main(){
ios::sync_with_stdio(false);
cin>>t;
for(int cas=1;cas<=t;cas++){
maxn=sum=0;auto itk=q.end();
cin>>d>>n>>k;
for(int i=1;i<=n;i++){
cin>>h>>s>>e;
a[s].push(h);b[e].push(h);
}
for(int i=1;i<=d;i++){
while(!a[i].empty()){
ll cur=a[i].front();a[i].pop();
q.insert(cur);
if(q.size()<=k) itk=q.end(),itk--,sum+=cur;
else if(cur>*itk) sum-=*itk,itk--,sum+=cur;
}
maxn=max(maxn,sum);
while(!b[i].empty()){
ll cur=b[i].front();b[i].pop();
auto p=q.find(cur);
if(q.size()<=k) sum-=cur;
else if(cur>=*itk) itk++,sum-=cur,sum+=*itk;
q.erase(p);
}
}
printf("Case #%d: %lld\n",cas,maxn);
}
return 0;
}
|