题目描述

难度分:$1600$

输入$n(1 \leq n \leq 2 \times 10^5)$，$A(n≤A≤sum(d))$和长为$n$的数组$d(1 \leq d[i] \leq 10^6)$。

有$n$个骰子，第$i$个骰子可以掷出$1$到$d[i]$中的任意整数。

掷出这$n$个骰子后，只告诉你所有骰子的数字之和为$A$。

对于每个骰子，输出这个骰子不可能掷出的数字有多少个。

输入样例$1$

2 8
4 4

输出样例$1$

3 3

输入样例$2$

1 3
5

输出样例$2$

4

输入样例$3$

2 3
2 3

输出样例$3$

0 1

算法

数学+二分

先求出数组$d$的总和$s$，然后考虑每个骰子能取什么点数。当遍历到$d[i]$时，其他所有骰子最多能够掷出的点数之和为$other=s-d[i]$，最少能掷出的点数为$n-1$，此时如果第$i$个骰子掷出$j$点，那么所有骰子的点数之和就在区间$[n-1+j,s-d[i]+j]$之中，因此我们只需要保证$A$在这个区间内就行了。

$s-d[i]+j \geq A$得到$A-other \leq j$，$A \geq n-1+j$得到$j \leq A-n+1$。二分找到两个端点$left$和$right$，骰子$i$不可能得到的点数就有$n-(right-left+1)$个。

复杂度分析

时间复杂度

遍历了$d$数组，对于每个$d[i]$，都在$[1,d[i]]$范围内进行了两次二分，时间复杂度为$O(log_2max(d))$。因此，算法整体的时间复杂度为$O(nlog_2max(d))$

空间复杂度

除了输入的数组$d$之外，只使用了有限的几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 200010;
LL n, A, s, d[N];

int main() {
    scanf("%lld%lld", &n, &A);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &d[i]);
        s += d[i];
    }
    for(int i = 1; i <= n; i++) {
        LL other = s - d[i];
        int l = 1, r = d[i], right = 0;
        while(l <= r) {
            int mid = l + r >> 1;
            if(mid <= A - n + 1) {
                right = mid;
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }
        l = 1, r = d[i];
        int left = 0;
        while(l <= r) {
            int mid = l + r >> 1;
            if(mid >= A - other) {
                left = mid;
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        printf("%d ", d[i] - (right - left + 1));
    }
    return 0;
}