CF1234A Equalize Prices Again 题解

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)));
	}
}
上一篇:【DB笔试面试694】在Oracle中,什么是oratop工具?


下一篇:利用 r2 逆向分析框架分析 Windows Minidumps