[ABC302D] Impartial Gift

题面翻译

一个人要送礼物给另外两个人，现有 $n$ 件礼物要选一件送给第一个人，价值分别为 $a_1,a_2,\cdots,a_n$，有 $m$ 件礼物要选一件送给第二个人，价值分别为 $b_1,b_2,\cdots,b_m$。求在两件礼物之差不超过 $d$ 的情况下，价值总和的最大值。

题目描述

高橋君は青木君とすぬけ君に $ 1 $ つずつ贈り物を送ることにしました。
青木君への贈り物の候補は $ N $ 個あり、 それぞれの価値は $ A_1,\ A_2,\ \ldots,A_N $ です。
すぬけ君への贈り物の候補は $ M $ 個あり、 それぞれの価値は $ B_1,\ B_2,\ \ldots,B_M $ です。

高橋君は $ 2 $ 人への贈り物の価値の差が $ D $ 以下になるようにしたいと考えています。

条件をみたすように贈り物を選ぶことが可能か判定し、可能な場合はそのような選び方における贈り物の価値の和の最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ M $ $ D $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ B_1 $ $ B_2 $ $ \ldots $ $ B_M $

输出格式

高橋君が条件をみたすように贈り物を選ぶことができる場合、 条件をみたし、かつ価値の和が最大になるように贈り物を選んだ時の価値の和を出力せよ。 高橋君が条件をみたすように選ぶことができない場合、$ -1 $ を出力せよ。

样例 #1

样例输入 #1

1
2
3
2 3 2
3 10
2 5 15

样例输出 #1

1
8

样例 #2

样例输入 #2

1
2
3
3 3 0
1 3 3
6 2 7

样例输出 #2

1
-1

样例 #3

样例输入 #3

1
2
3
1 1 1000000000000000000
1000000000000000000
1000000000000000000

样例输出 #3

1
2000000000000000000

样例 #4

样例输入 #4

1
2
3
8 6 1
2 5 6 5 2 1 7 9
7 2 5 5 2 4

样例输出 #4

1
14

提示

制約

  • $ 1\leq\ N,M\leq\ 2\times\ 10^5 $
  • $ 1\leq\ A_i,B_i\leq\ 10^{18} $
  • $ 0\leq\ D\ \leq\ 10^{18} $
  • 入力はすべて整数

Sample Explanation 1

高橋君は贈り物の価値の差を $ 2 $ 以下にする必要があります。 青木君に価値 $ 3 $, すぬけ君に価値 $ 5 $ の贈り物を渡すと条件をみたし、価値の和としてはこのときが最大となります。 よって、$ 3+5=8 $ を出力します。

Sample Explanation 2

条件をみたすように贈り物を選ぶことは不可能です。 また、同一人物に対して、同じ価値の贈り物が複数存在することもあります。

Sample Explanation 3

答えが $ 32 $ bit整数型の範囲に収まらないことがあることに注意してください。

题解

题目解析

这道题一开始不知道如何找到最大的那个值,起初想用双指针,结果还是不太会.暴力的方法大小也还是 $O(NM)$ 同样也会炸= =.

这道题还是看了jiangly的代码,才明白这道题确实非常简单,是我对于STL的熟练度有问题.jiangly使用了upper_bound()这个函数,找到每个$A_i$对应差小于等于 $d$ 的 $B_i$ 最大值,利用这个函数扫一遍答案就出来了= =,显然时间复杂度$O(n\log n)$.

AC代码

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
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#define endl "\n"
using namespace std;

typedef long long ll;
const int MAXN = 2e5+10;

ll a[MAXN],b[MAXN];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll n,m,d,ans=-1;
	cin >> n >> m >> d;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<=m;i++) cin >> b[i];
	sort(a+1,a+n+1),sort(b+1,b+m+1);
	for(int i=1;i<=n;i++){
		auto p = upper_bound(b+1,b+1+m,a[i]+d);//它返回的是第一个超过a[i]+d的值的位置.
		ll k = *(p-1);
		if(k >= a[i] - d)//因为可能返回了b+1+m的位置(也就是没找到),此时的k可能不符合两者之差小于d的情况.
			ans = max(ans,a[i]+*(p-1));
	}
	 cout << ans << endl;
	return 0;
}

Remark

  • upper_bound([迭代器起点],[迭代器终点],[value]) 返回第一个大于value值的位置,如果没找到则返回[迭代器终点] .
  • 使用 upper_bound() 前必须进行排序,函数运行原理为二分查找.