[C++]白駿2485号:林蔭樹

6339 ワード
せいすう論 白駿 ユークリッドアークほう テキストリンク
質問リンク
2485号:並木
問題の概要
ルートツリーの基点からの距離を指定します.その間に街路樹を植えて、各街路樹の間の間隔を等しくします.そのため、植える街路樹の最高価格を見つける必要がある.
方法
最大公約数で解決できる
まず,本来植えられていた街路樹間の間隔の最大公約数を求める.また、この最大公約数に対応する各間隔に横数を追加する必要があります.これにより、横数の最小数で同じ間隔を確保できます.
各間隔には、(街路樹間隔)/(最大公約数)-1の横数が必要です.これらを合わせると答えが得られます.
最大公約数はユークリッドアーク除去法により求めることができる.
コード#コード#
#include <bits/stdc++.h>

using namespace std;

int gcd(int a, int b)
{
	if (a < b)
		swap(a, b);
	return (a % b == 0 ? b : gcd(b, a % b));
}

int main(void)
{
	int n, res = 0;
	cin >> n;

	vector<int> v(n), diff;
	for (auto& i : v)
		cin >> i;

	for (int i = 0; i < n - 1; i++)
		diff.push_back(v[i + 1] - v[i]);

	int g = gcd(diff[0], diff[1]);
	for (int i = 2; i < diff.size(); i++)
		g = gcd(g, diff[i]);
;
	for (auto& i : diff)
		res += i / g - 1;

	cout << res << endl;
	return 0;
}
のビューアとコンバータ-フラスコ＆簡単なデータテーブルによって供給
航空機大戦-GameGoods商品の実現