原题链接
题目描述
输入描述
输出描述
输入样例
235 10 85 2 125 64 4输出样例
2 31 21 32 21 1题目大意：给定两个数组 a 和 b，其中数组 a 的第 i 个元素即为第 i 个队伍的对应分数，每个队伍的最终得分为数组 a 中的对应分加上数组 b 中的任意一项，现求每个队伍的最好名次和最差名次分别是多少。其中，队伍名次的计算公式为 1 + 比分严格大于该队伍的队伍数量。
不难得知每个队伍的最高得分和最低得分分别是加上 b 中的最高分和最低分，再将数组 b 中剩余的分给其他队伍以凑得最大满足条件的数量，其中分为这两种情况进行讨论：
取最高排名时： 让现存分数最小的队伍依次与数组 b 中现存的最高分进行匹配，若分数最小队伍与最高分相加仍大于当前队伍的总分，则可推出现存的最高分不论与哪个队伍相匹配都无法满足需求（因为其它的剩余队伍得分都会比最小队伍大，相加后的总分只会更高），因此该最高分可不必再进行讨论，并令分数最小队伍与次高分匹配直至符合要求。
取最低排名时： 同样令现存分数最小的队伍依次与数组 b 中现存的最高分进行匹配，若分数最小队伍与最高分相加仍小于当前队伍的总分，则可推出分数最小队伍不论与哪个分数匹配都无法满足需求（因为其它分数都比现存最高分小，相加后的总分只会更低），因此该队伍可不必再进行讨论，并令该最高分与次小队伍匹配直至符合要求。
参考代码：
#include<bits/stdc++.h>using namespace std;typedef long long ll;int t,n;struct node{ ll num,val;}a[5001]; int ans[5001][2];ll b[5001];bool cmp(node x,node y){ return x.val<y.val;}int maxx(int k){ int N=a[k].val+b[1],cnt=0; int p=1;int q=2;while(p<=n && q<=n){if(p==k){p++;continue;} if(a[p].val+b[q]<=N){p++;cnt++;}q++;} return cnt;}int minn(int k){ int N=a[k].val+b[n];int i=1,j=1,c=1;while(i<=n){if(i==k){i++;continue;}if(a[i].val >N){c++;i++;continue;}if((a[i].val+b[j])>N){j++;c++;}i++;}return c;}int main(){ scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%lld",&a[i].val); a[i].num=i; } for(int i=1;i<=n;i++) scanf("%lld",&b[i]); sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++){ int num=a[i].num; ans[num][0]=n-maxx(i); ans[num][1]=minn(i); } for(int i=1;i<=n;i++){ printf("%d %dn",ans[i][0],ans[i][1]); } } return 0;}