连接：https://codeforces.com/problemset/problem/1976/C
题目：
思路：
我们可以想象这个是两个队列，采用两个前缀和数组：suma和sumb记录前几个完全按照大小分配成程序员/测试员的个数（指不考虑每个种类人数限制的情况），然后二分查找到最小满足的种类。这里采用ra和rb表示，然后哪个更小取哪个为末基数x，对∀i∈(1,min(ra,rb)),可以取ans+=max(a[i],b[i])，并且当i == 去掉的数id时减去对应的maxn；然后在x之后所有的都会被并为一种类型：如果是ra小，说明programmer满员了，那么都取b的值；反之亦然。
刚开始tle了，所以必须采用前缀和，比较特殊用了三个前缀和：maxn的前缀和 + a的前缀和 + b的前缀和
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
#define IOS ios::sync_with_stdio(false), cin.tie(0) ,cout.tie(0)
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll a[N],b[N],suma[N],sumb[N];
ll n, m;
ll qzha[N], qzhb[N],maxn[N];
int main()
{
IOS;
int t; cin >> t;
while (t--)
{
cin >> n >> m;
for (int i = 1; i <= m + n + 1; i++) { cin >> a[i]; qzha[i] = a[i] + qzha[i - 1]; }
for (int i = 1; i <= m + n + 1; i++) { cin >> b[i]; qzhb[i] = b[i] + qzhb[i - 1]; //b的前缀和}
for (int i = 1; i <= m + n + 1; i++)
{
suma[i] = a[i] > b[i]; suma[i] += suma[i - 1];//a比b大
sumb[i] = a[i] < b[i]; sumb[i] += sumb[i - 1];
maxn[i] = max(a[i], b[i]) + maxn[i-1];//前缀和
}
if (!n)
{
ll numa = 0;
numa = qzhb[n + m + 1];
for (int i = 1; i <= n + m + 1; i++)cout << numa - b[i] << ' ';
}
else if (!m)
{
ll numa = 0;
numa = qzha[n + m + 1];
for (int i = 1; i <= n + m + 1; i++)cout << numa - a[i] << ' ';
}
else
{
for (int getaway = 1; getaway <= n + m + 1; getaway++)
{
int la = 1, ra = m + n + 1;
while (la < ra)
{
int mid = (la + ra) / 2;
int dt = suma[getaway] - suma[getaway - 1];//二分查找，注意要减掉getaway的数
int cmp = suma[mid];//cmp就是到mid的时候有几个programmer
if (mid >= getaway)
{
cmp -= dt;
}
if (cmp >= n)ra = mid;
else la = mid + 1;
}
int lb = 1, rb = m + n + 1;//对b序列二分查找
while (lb < rb)
{
int mid = (lb + rb) / 2;
int dt = sumb[getaway] - sumb[getaway - 1];
int cmp = sumb[mid];
if (mid >= getaway)cmp -= dt;//同上
if (cmp >= m)rb = mid;
else lb = mid + 1;
}
ll cnt = 0;
if (rb < ra)
{
cnt += qzha[m + n + 1] - qzha[rb] + maxn[rb];//前缀和的运用
if (getaway >= rb + 1)cnt -= a[getaway];
else cnt -= maxn[getaway]-maxn[getaway-1];
}
else
{
cnt = maxn[ra] + qzhb[m + n + 1] - qzhb[ra];
if (ra + 1 <= getaway)cnt -= b[getaway];
else cnt -= maxn[getaway]-maxn[getaway-1];
}
cout << cnt << ' ';
}
}
cout << '\n';
}
return 0;
}