Trader Problem

题目大意

你有$n$个物品，第$i$-th个物品价值为$a_i$，商人有$m$个物品，第$i$-th个物品价值为$b_i$，你可以将自己的某个物品，假设价值为$a_i$，与商人手中价值不超过$a_i+k$的物品交换。现在有$q$次询问，每次给定一个$k$值，求能通过以上操作能使手中物品价值之和到达的最大值。

解题思路

将物品价值从大到小排序后进行合并。相邻插值小于$k$即可进行合并。同时拿并查集维护可选数。可以对需要查询的$k$进行排序，减小复杂度。具体实现看代码。

参考代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
#define maxn 400100
#define int long long
typedef __int128_t int128;
using namespace std;
const double eps=1e-8;
int f[maxn];  //并查集
int sz[maxn],sum[maxn];   //当前集合可取数的数量和排序后的前缀和
pair<int,int>a[maxn],que[maxn];   //物品和询问,离线
map<int,vector<int>>num;  //相邻物品可合并的值
int ans[maxn];
int find(int x){
    if(f[x]!=x)  f[x]=find(f[x]);
    return f[x];
}
void solve(){
    int n,m,q,res=0;
    cin >> n >> m >> q;
    for(int i=1;i<=n+m;++i)  cin >> a[i].first,a[i].second=i;
    sort(a+1,a+n+m+1);
    for(int i=1;i<=n+m;++i){
        if(a[i].second<=n)  res+=a[i].first;
        sz[i]=(a[i].second<=n);
        f[i]=i;  sum[i]=sum[i-1]+a[i].first;
        if(i>1)  num[a[i].first-a[i-1].first].push_back(i-1);
    }
    for(int i=1;i<=q;++i)  cin >> que[i].first,que[i].second=i;
    sort(que+1,que+q+1);
    auto it=num.begin();
    for(int i=1;i<=q;++i){
        if(que[i].first==que[i-1].first)  {ans[que[i].second]=res;continue;}
        while(it!=num.end()&&it->first<=que[i].first){
            for(auto u:it->second){   //合并
                int a=find(u),b=find(u+1);
                res-=sum[a]-sum[a-sz[a]]+sum[b]-sum[b-sz[b]];
                f[a]=b;  sz[b]+=sz[a];
                res+=sum[b]-sum[b-sz[b]];
            }
            ++it;
        }
        ans[que[i].second]=res;
    }
    for(int i=1;i<=q;++i)  cout << ans[i] << '\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}