【题解】21 ZR联赛集训 d6 夏令营

发表于 分类于 阅读次数： Valine： 本文字数： 455 阅读时长 ≈ 2 分钟

题目链接（正睿）

题目大意

给出个活动和每个活动的吸引力和开始和结束时间，总天数为。规定一天最多参加个活动，求哪一天的吸引力总和最大。

$1\le n \le 3 \times 10^5,~1 \le D \le 3\times 10^5$

分析

将所有开始、结束的时间标记一下，使用动态维护每个时间点吸引力前大的和。具体地，记录每一个时间点第大的数是多少，如果现在要插入的数比大，那么插入该数字，左移一位，否则不用管，最后维护一下前缀和即可。删除数字是把这个过程逆过来即可。

实现

主要部分就是动态维护的过程。

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;
}