Problem Description
TI10 and ICPC World Finals 2020, which will be held earlier? Take a bet!
The International(TI) is the biggest and most prestigious event of Dota2 and is commonly held annually in August. The Dota2 teams should try to earn points to be eligible to compete in TI. There are two ways of earning points, first is by competing in the regional contests, second is by competing in the tournaments, where all teams are gathered to compete together and earn points according to their rank in the tournament. A team's final score is the sum of scores from both the regional contests and tournaments.
Now that the regional contests have finished, there are n teams taking part, and the ith team has earned ai points from the regional contests. Also, the team that gets the ith rank in the tournament can gain bi points.
cyz is a huge fan of Dota2. So before the tournament starts, he will predict the final rank of all teams. cyz wants to know, for each team, what's its best possible rank and its worst possible rank after the tournament finishes.
If a team has a final score equal to x, its rank is defined as one plus the number of teams with a strict higher score than it. For example, if the final score of four teams are 700,500,500,300 respectively, then their final ranks are 1,2,2,4, respectively.
Input
The first line contains a number T(1≤T≤20), denoting the number of test cases.
The first line of each test case contains one number n(1≤n≤5000), denoting the number of different teams that participate in the regional contests and tournaments.
The next line contains n integers a1,a2,…,an(0≤ai≤109), denoting the points of each team before the tournament starts.
Then follows one line containing n integers b1,b2,…,bn(0≤bn≤bn−1≤...≤b1≤109), where bi denotes the number of points a team would get if ranking ith in the tournament.
It is guaranteed that there are at most 8 cases with n>100.
Output
For each test case, output n lines, where the ith line contains two integers besti,worsti(1≤besti≤worsti≤n), denoting the best possible and worst possible rank a team would get after the tournament finishes.
Sample Input
2
3
5 10 8
5 2 1
2
5 6
4 4
Sample Output
2 3
1 2
1 3
2 2
1 1
既然是求每个组的最高和最低排名，而且这个题没有什么计算贡献的地方，那么枚举每个team是必不可少的了。注意到n的范围是5e3，且最多有8个case的n超过100，赛中时限是2s，那么基本可以确定要写一个(O(n^2))的算法出来。既然已经枚举了team，循环内要做的就是针对这个team，(O(n))地求出来它的最高排名和最低排名。这两者求法是类似的，不妨以求最高可能排名为例。既然要求的是最高可能排名，根据题意就该让当前的team（假设为x）的总分（a[x] + b[?]）尽可能高，那么肯定要把b[1]的值（最大的）分配给x。剩下的就是要给n - 1个team和n - 1个b数组的值进行分配使得总分大于a[x] + b[1]的team尽可能少（这样才能让x的排名尽可能靠前）。首先，如果一个team（设为i）的初始分数a[i]就大于x的最终分数a[x] + b[1]的话，那么无论如何这个team的排名都会比x靠前，根据田忌赛马的思想，这时候我们就给它分配尽可能高的分数（反正这个team的最终分数一定比x高，那么不妨靠它消耗大的b数组的值），从而降低初始分数低于x的组通过排位分反超的概率。然后就是给剩下的team分配剩下的b数组的值了。一个显然的做法是对于每个剩下的组y从当前的b数组的剩下的值中找到和a[i]相加不大于a[x] + b[1]的那个最大的值进行配对，然后把这个值从b数组删除，可以用二分做到，但复杂度显然是不允许的。然而注意到，对于一个确定的a[i]，假设a[i] + b[z] > a[x] + b[1]，那么对于比a[i]大的a[j]而言，也一定存在a[j] + b[z] > a[x] + b[1]，所以对于a[j]来说b[z]这个值在枚举到a[i]的时候就已经被排除了，也就是说这里是有单调性的，可以(O(n))地进行求解。
上面可能有亿点抽象，最后这一个过程可以转化成这么一个问题：有两个均含有n个元素的数组a和b，让他们两两配对使得和（即a[i] + b[j]）大于x的数对尽可能少（或者小于等于x的数对尽可能多）。做法就是将a和b从大到小排序，然后双指针法先从小到大枚举a[i]，另一个指针从大到小枚举b，直至遇到一个元素b[j]满足a[i] + b[j] <= x，此时将a[i]和b[j]配对（这样能够让和小于等于x的数对尽可能多），然后a数组指针继续移动...这个过程之所以能够以(O(n))的复杂度完成就是因为b数组的指针不用回退。
具体细节见代码。
#include <bits/stdc++.h>
#define int long long
#define tm tmd
using namespace std;
int n, a[50005], b[50005];
struct team {
int id, sc;//id是初始位置 sc是score分数
bool operator<(const team &o) const {
return sc > o.sc;//从大到小排序
}
} tm[50005];
int ans1[50005], ans2[50005];
signed main() {
int t;
cin >> t;
while(t--) {
scanf("%lld", &n);
for(int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
tm[i].id = i, tm[i].sc = a[i];
}
sort(tm + 1, tm + n + 1);
for(int i = 1; i <= n; i++) {
scanf("%lld", &b[i]);
}
for(int i = 1; i <= n; i++) {
int high = tm[i].sc + b[1];//i这个组取得最好排名的应该有的最高分数
int cnt1 = 0, pos = 2;//cnt1是在这个组前面的组的数量，pos是b数组的指针，因为b[1]已经被用了，所以从2开始
for(int j = 1; j <= n; j++) {
if(i == j) continue;
if(tm[j].sc + b[n] > high) pos++, cnt1++;//对于这种一定比i牛逼的team，直接让它消耗更大的b值
else {
if(i == j) continue;
int p = pos;//剩下的可以用的b数组的值从pos到n
int res = n - pos + 1, cnt2 = 0;//cnt2为和小于等于high的数对的数量，最终要让这个数尽可能大
for(int k = n; k >= j; k--) {//从小到大枚举a数组的值
if(i == k) continue;
while(b[p] + tm[k].sc > high) p++;//b数组指针不断往小移动 直到满足条件
if(p > n) break;//越界了
cnt2++;//移动到合适的位置以后说明配成了一对和小于等于high的数对
p++;
}
cnt1 += (res - cnt2);//加上总的剩下的减去和小于等于high的
break;
}
}
ans1[tm[i].id] = cnt1 + 1;//别忘了求的是排名
//下面同理，也有单调性，不同的是要让和大于low的尽可能多
int low = tm[i].sc + b[n];
int cnt2 = 0;
pos = n - 1;
for(int j = 1; j <= n; j++) {
if(i == j) continue;
if(tm[j].sc > low) pos--, cnt2++;
else {
int up = pos;//b数组指针，从小到大移动
for(int k = j; k <= n; k++) {
if(k == i) continue;
if(up < 1) break;
//b是降序的 单调性
while(b[up] + tm[k].sc <= low) up--;//a[i] + b[j]都不大于high，那么比a[i]小的a[k] +b[j]更不可能大于high，因此b数组的指针移动也是单调的
if(up < 1) break;
cnt2++;
up--;
}
break;
}
}
ans2[tm[i].id] = cnt2 + 1;
}
for(int i = 1; i <= n; i++) {
printf("%lld %lld
", ans1[i], ans2[i]);
}
}
return 0;
}
//ai bi可以是0！！！！！
// 1
// 10
// 0 0 1 0 0 1 1 0 1 0
// 1 1 1 1 1 0 0 0 0 0
// 1
// 10
// 1 5 4 2 3 5 3 2 2 1
// 3 3 3 3 2 2 2 2 2 1
// 1
// 3
// 5 10 8
// 5 2 1
// 1
// 3
// 0 1 2
// 999 1 1