CF793A Oleg and shares 题解

Content

有 \(n\) 支股票，第 \(i\) 支股票原价为 \(a_i\) 卢布。每秒钟可能会有任意一支股票的价格下降 \(k\) 卢布，以至于降到负数。求所有股票的价格均变得相同所要经过的最短时间，或者这不可能。

数据范围：\(1\leqslant n\leqslant 10^5,1\leqslant k,a_i\leqslant 10^9\)。

Solution

因为股票的价格只能够下降，因此肯定是要求最后都要降到 \(n\) 支股票的价格的最小值 \(x\)。然后，因为每秒下降 \(k\) 卢布，所以，只要有 \(i\) 使得 \(k\nmid a_i-x\) 那么就不可能满足题目的条件，否则，答案就是 \(\sum\limits_{i=1}^n\dfrac{a_i-x}{k}[a_i\neq x]\)。

Code

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <iostream>

using namespace std;

int a[100007];

long long ans;

int main() {

	int n, k;

	scanf("%d%d", &n, &k);

	for(int i = 1; i <= n; ++i)	scanf("%d", &a[i]);

	sort(a + 1, a + n + 1);

	for(int i = 2; i <= n; ++i) {

		if((a[i] - a[1]) % k)	return printf("-1"), 0;

		ans += (a[i] - a[1]) / k;

	}

	printf("%lld", ans);

}

巴特西

CF793A Oleg and shares 题解

Content

Solution

Code

最新文章

热门文章