题解 CF1679A【AvtoBus】

Anguei · 2022-05-15 21:06:54 · 题解

题意

有两种类型的公交车，第一种车需要 4 个轮子，另一种需要 6 个轮子。

现在给你 n 个轮子，要求恰好装到 m 辆公交车上。问 m 的最小值和最大值。

分析

首先考虑无解情况：

• 如果给定的轮子不足 4 个，则一辆车都装不好，无解。
• 如果给的轮子数量是奇数，则无论如何都不能恰好地装上车。

其余情况：方程 4x + 6y = 2k \ (k \geq 2) 一定有正整数解。其中 x+y = m。

要让 x 取最小值，就让尽可能让每辆车消耗 6 个轮子；反之，要取最大值，就尽可能多的让每辆车装 4 个轮子。

代码

void solution() {
  ll n;
  read(n);
  if (n < 4) return print(-1);
  if (n & 1) return print(-1);
  if (n % 6 == 0 && n % 4 == 0) return print(n / 6, n / 4);
  ll y = n / 4;
  ll x = n / 6 + int(n % 6 != 0);
  return print(x, y);
}