However, Dragon's mom comes back home again and close the TV, driving Dragon to his homework, and find out the paper with scores of all competitors. Dragon's mom wants to know how many competition Dragon watched, but it's hard through the paper. Here comes the problem for you, given the scores of all competitors, at least how many competitions had Dragon watched?
Input The first line of input contains only one integer T(<=10), the number of test cases. Following T blocks, each block describe one test case.
For each test case, the first line contains only one integers N(<=100000), which means the number of competitors. Then a line contains N integers (a 1,a 2,a 3,...,a n).a i(<=1000000) means the score of i-th competitor.
Sample Input
1 3 2 3 4
Sample Output
Case #1: 5 题意：给你n个初值为0的数，每次你可以任选两个做加操作，可以是0或者1，求最少的操作使的这n个数变为题目所给的n个数 思路：贪心，显然我们是尽量两个都做+1操作，那么我们先求出最大的，让他带着+1，然后是前n-1个数的和如果小于的话，最小操作就是最大的数，否则还要进行操作
#include#include #include #include typedef __int64 ll; using namespace std; int main() { int t, n, cas = 1; scanf("%d", &t); while (t--) { scanf("%d", &n); int Max = -1, a; ll sum = 0; for (int i = 0; i < n; i++) { scanf("%d", &a); sum += a; if (Max < a) Max = a; } sum -= Max; ll ans; if (Max >= sum) ans = Max; else ans = Max + (sum - Max + 1) / 2; printf("Case #%d: %I64d\n", cas++, ans); } return 0; }