CodeForces

题目链接

题目大意

  有n个人,两局比赛,每场比赛每个人的得分构成一个排列,现在一个人两场的得分是x与y,问这个人最少/最多排第几名,相同分数的人并列,并且询问的人在相同分数的人中排最后。

解题思路

  先考虑最靠后的排名,如果想让这个人排名尽可能的靠后,那么就让尽可能多的人排在他的前面(废话),也许让大家都和他相等是个好方法?我们找一个得分为x+y的人,他在第一场得1分, 那么他最多在第二场得x+y-1分,如果他在第一场得2分,那么他在第二场最多得x+y-2分,这样我们可以算出啊,得分为x+y的人最多有x+y-1个(第一个人得1+(x+y-1)分,所以最小的数字是1,最大的数字是x+y-1,两边各有x+y-1个数相联系),当然,x+y-1不应该超过n。
  然后考虑最靠前的排名, 我们想尽可能的让其他人的得分大一些以使他们的排名更靠后,考虑第一场得分为1的人, 如果他第二场得n分还是小于等于x+y的话,那么直接让他第二场也得1分,即这个人没法靠后,就让他多消耗一些数值比较小的分数,同样,得分为2的人也如此,这样,我们可以算出得分小于等于x+y的人至少有x+y-n+1个(假设某个人得分恰好为x+y, 在第二场得n分的情况下,第一场至少需要x+y-n分,因为这个人的得分为x+y,所以我们还要再往后一名,最后结果为x+y-n+1),当前,x+y-n+1也应该不超过n且不小于1。
  是不是发现了哪里不对劲?我们好像并没有把得分为x+y的人考虑进去,事实上,在考虑这个人得分最靠后的时候,我们考虑的是所有得分等于x+y的情况,所以这个人也被包含了进去。而考虑这个人排名在最靠前的时候,如果他的得分情况就是和我们假设的得分恰好为x+y的人一样,那就让下一个人第二场少拿一分(否则得分还是x+y,依然小于等于这个人),然后下个人之后的所有人的得分都能比x+y大了,最终的排名依然是max(1, min(x+y-n+1, n))。

代码

int main() {
    int __; cin >> __;
    while(__--) {
        ll n, x, y; cin >> n >> x >> y;
        ll a1;
        if (x+y<n) a1 = 1;
        else a1 = min(x+y-n+1, n);
        ll a2 = min(x+y-1, n);
        cout << a1 << ' ' << a2 << endl;
    }
    return 0;  
}
原文地址:https://www.cnblogs.com/shuitiangong/p/14551957.html