Polycarpus‘ Dice CF534C 泡利的骰子 详细 翻译

原题链接 位于CodeForceshttps://codeforces.com/problemset/problem/534/C

题目

        泡利有n个骰子d1,d2,...dn。第i个骰子能显示的点数为1到di。泡利扔出所有的骰子并且点数总和为A。阿格里并不能看到每个骰子的点数，但她知道总和A与每个骰子的最大点数d1,d2,...dn。不过她认为这已经能让她得到以下结论：第i个骰子不能为r。比如当泡利有两个六面的骰子并且总点数为11时，阿格里能确定每个骰子的点数都不能小于5（不然的话另一个骰子的点数就要至少为7了，这当然不可能）

        对于确定的总点数A，我们都要找出每一个骰子不可能得到的点数。

输入

第一行包含两个整数n，A（ 1 ≤ n ≤ 2·10^5, n ≤ A ≤ s），骰子的数量与它们的总点数。并且s为所有骰子的最大点数和。

第二行包含n个整数d1,d2,...dn (1 ≤ di ≤ 10^6)，di就是第i个骰子的最大点数。

输出

打印n个整数b1, b2, ..., bn，bi就是第i个骰子不能得到的点数的个数。

样例

输入

2 8
4 4

输出

3 3 

注意：每个骰子都不能为1，2，3

输入

1 3
5

输出

4 

注意：骰子不能为1，2，4，5

输入

2 3
2 3

输出

0 1 

注意：第一个骰子不管是什么(1或2)，第二个骰子都有可能使总点数为3

第二个骰子不能为3，否则不管第一个骰子为1或是2都会使总和大于3，即不等于3

 其实这个题目只需要得出两个式子

即 不管其他骰子的点数如何 都会使点数总和小于A的点数个数

和 不管其他骰子的点数如何 都会使点数总和大于A的点数个数

要求第一条，只需要将A减去其他骰子所能达到的最大点数，就是这个骰子所需要的最小点数，只要比这个点数小，那么就是不可能取到的点数

要求第二条，只需使在所有其他骰子都是最小点数即1的情况下，这个骰子的点数仍使总和大于A即可

两者相加就是所有不能取到的点数的个数了！

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;// 骰子不可能的取值int num[200010]; // 骰子的最大值int main()
{int i, j;long long n, A;long long sum = 0;scanf("%lld%lld", &n, &A);for (i = 0; i < n; i++){scanf("%d", &num[i]);sum += num[i];}long long ans;long long t;for (i = 0; i < n; i++){t = A - (sum-num[i]) - 1; // 第一条要求ans = t>0?t:0;t = num[i] - (A-(n-1)); // 第二条要求ans += t>0?t:0;cout << ans << ' ';}//getchar();getchar();return 0;
}