给定 (n) 个正整数 (a_i,cdots,a_n) 和 (m) 个正整数 (b_1,cdots,b_m)，进行 (frac{n-1}{m-1}) 次操作，每次选择 (a) 中的 (m) 个正整数 (x_1,cdots,x_m)，删去它们，加入 (max{x_i+b_i})，求最后得到的数的最小值。
(n,mle 5cdot 10^4)，((m-1)mid(n-1))，(a_ile 10^8)，(b_ile 10^7)。
考虑二分答案并倒着做：设最后剩下 (x)，每次操作选择 (x) 拆成 (x-b_i)，问最后能不能对应地 (ge a_i)。
不妨将 (a,b) 都排序，考虑更一般的集合 (S,T)，(|S|le |T|)，(|S|equiv|T|pmod{m-1})，问 (S) 能不能拆成 (T)。
若 (|S|=|T|)，则只需判断将 (S,T) 排序之后是否有 (s_ige t_i)。
若 (|S|=0land |T|>0)，无解。
若 (|S|<|T|)，则
- 若 (max S<max T)，无解。
- 若 (max Tle max S<b_1+max T)，将 (S) 的最大元拆掉就不能对应了，所以与 (T) 的最大元对应的元素不能拆，找一个 lower_bound 匹配即可。
- 若 (max Sge b_1+max T)，则 (S) 的最大元拆掉不劣。
模拟这个过程即可，时间复杂度 (O(nlog nlog V))。
#include<bits/stdc++.h>
using namespace std;
const int N = 50003;
template<typename T>
void rd(T &x){
int ch = getchar(); x = 0;
for(;ch < '0' || ch > '9';ch = getchar());
for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
}
int n, m, a[N], b[N];
multiset<int> S;
multiset<int>::iterator it;
bool check(int x){
S.clear(); S.insert(x);
int now = n;
while(!S.empty() && S.size() < now){
int tmp = *--(it = S.end());
if(tmp >= a[now] + b[1]){
S.erase(it);
for(int i = 1;i <= m;++ i)
S.insert(tmp-b[i]);
} else if(tmp >= a[now])
S.erase(S.lower_bound(a[now--]));
else return false;
}
if(S.size() == now){
for(int i = 1;i <= now;++ i, S.erase(it))
if(*(it = S.begin()) < a[i]) return false;
return true;
} return false;
}
int main(){
rd(n); rd(m);
for(int i = 1;i <= n;++ i) rd(a[i]);
for(int i = 1;i <= m;++ i) rd(b[i]);
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
int l = a[n], r = 260000000, md;
while(l < r) check(md = l+r>>1) ? r = md : l = md+1;
printf("%d
", l);
}