Content
有 \(n\) 个商品,第 \(i\) 个商品价值为 \(a_i\),求能够将所有商品卖出后不亏本且赚的钱最少(可以不赚)的价格(必须为整数)。
数据范围:\(q\) 组数据。\(1\leqslant q\leqslant 100,1\leqslant n\leqslant 100,1\leqslant a_i\leqslant 10^7\)。
Solution
这题的结论是比较显然的。设 \(n\) 个商品的平均价格为 \(\bar{a}\),则答案即为 \(\geqslant\bar{a}\) 的最小整数。
证明如下:
设每件商品售价为 \(x(x\in \text{Z})\)(\(\text{Z}\) 表示整数集),则要使的卖出所有商品后不亏本,必须要有
\[n\cdot x-\sum\limits_{i=1}^n a_i\geqslant 0 \]又因为
\[\sum\limits_{i=1}^n a_i=n\cdot\bar{a} \]所以
\[n\cdot x-n\cdot\bar{a}\geqslant 0 \]即
\[n\cdot x\geqslant n\cdot\bar{a} \]即
\[x\geqslant\bar{a} \]所以,必须让 \(x\) 为 \(\geqslant\bar{a}\) 的最小整数才能满足条件。
证毕。
因此,需要找到它们的平均数,然后将其向上取整即可。
Code
#include <cstdio>
#include <cmath>
using namespace std;
int t, n, a[1000007], sum;
int main() {
scanf("%d", &t);
while(t--) {
sum = 0;
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
sum += a[i];
}
printf("%d\n", (int)(ceil(sum * 1.0 / n)));
}
}