题解 | 买橘子

方法众多，以下给出五种。

方法一：完全背包

#include <iostream>
#include <vector>
#include <algorithm>

constexpr int inf = 1E9;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int n;
  std::cin >> n;

  std::vector<int> dp(n + 1, inf);
  dp[0] = 0;
  for(int i = 6; i <= n; i++){
    dp[i] = dp[i - 6] + 1;
    if(i >= 8){
      dp[i] = std::min(dp[i], dp[i - 8] + 1);
    }
  }

  std::cout << (dp[n] >= inf ? -1 : dp[n]) << "\n";

  return 0;
}

方法二：最短路bfs

#include <iostream>
#include <vector>
#include <queue>

constexpr int inf = 1E9;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int n;
  std::cin >> n;

  auto bfs = [&](){
    std::vector<int> dist(n + 1, inf);
    std::vector<bool> vis(n + 1);
    std::queue<int> q;
    q.push(n);
    vis[n] = true;
    dist[n] = 0;

    while(q.size()){
      auto u = q.front();
      q.pop();

      if(u == 0){
        return dist[u];
      }

      if(u - 8 >= 0 && !vis[u - 8]){
        dist[u - 8] = dist[u] + 1;
        vis[u - 8] = true;
        q.push(u - 8);
      }

      if(u - 6 >= 0 && !vis[u - 6]){
        dist[u - 6] = dist[u] + 1;
        vis[u - 6] = true;
        q.push(u - 6);
      }
    }

    return -1;
  };

  std::cout << bfs() << "\n";

  return 0;
}

方法三：暴力模拟

#include <iostream>
#include <vector>
#include <algorithm>

using i64 = long long;

constexpr int inf = 1E9;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int n;
  std::cin >> n;

  int ans = inf;
  for(int i = 0; i <= n / 8; i++){
    if((n - i * 8) % 6){
      continue;
    }
    int j = (n - i * 8) / 6;
    ans = std::min(ans, i + j);
  }

  std::cout << (ans == inf ? -1 : ans) << "\n";

  return 0;
}

方法四：扩展gcd

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

/*
 * 函数模板 exgcd
 * 可以处理 a, b, x, y为i64等情况
*/
template<typename T>
constexpr T exgcd(T a, T b, T& x, T& y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  T d = exgcd(b, a % b, y, x);
  y -= (a / b) * x;
  return d;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int n;
  std::cin >> n;

  int a = 6, b = 8, x, y;
  auto gcd = exgcd(a, b, x, y);

  if(n % gcd){
    std::cout << "-1\n";
    return 0;
  }

  int k = n / gcd;
  x *= k;
  y *= k;

  int u = b / gcd;
  int v = a / gcd;

  int l = std::ceil(-1. * x / u);
  int r = y / v;

  if(l > r){
    std::cout << "-1\n";
    return 0;
  }

  std::cout << ((x + l * u) + (y - l * v)) << "\n";

  return 0;
}

方法五：推结论

#include <iostream>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int n;
  std::cin >> n;

  std::cout << ((n % 2 || n < 6 || n == 10) ? -1 : (n + 6) / 8) << "\n";

  return 0;
}