c++ CodeChef和CodeForces上的最小硬币变化问题(动态编程实现)超过时间限制

eyh26e7m 于 2023-04-01 发布在其他

关注(0)|答案(2)|浏览(137)

我在CodeChef和CodeForces上遇到了最小硬币变化问题。在这两个网站上，我都使用DP提交了我的实现。这两个网站上的实现都给出了TLE错误。
不幸的是，我找不到这个问题的任何其他实现。
我正在链接问题- CodeChef -https://www.codechef.com/problems/FLOW005
CodeForces - https://codeforces.com/problemset/problem/996/A
下面是我的代码（CodeChef实现）-

int main() {
    int T{};
    std::cin >> T;
    for (int i = 1; i <= T; ++i) {
        int N{};
        std::cin >> N;
        std::vector <int> arr(N + 1);
        for (int i = 0; i < N + 1; ++i) {
            arr[i] = minCoins(i, arr);
        }
        std::cout << arr[N] << std::endl;
    }

    return 0;
}

minCoins函数-

int minCoins(int x, std::vector <int> arr) {
    if (x == 0)
        return 0;
    else if (x == 1 || x == 2 || x == 5 || x == 10 || x == 50 || x == 100)
        return 1;
    int min{ 1 + arr[x - 1]};
    if (x > 100)
        min = std::min(min, l + arr[x - 100]);
    if (x > 50)
        min = std::min(min, 1 + arr[x - 50]);
    if (x > 10)
        min = std::min(min, 1 + arr[x - 10]);
    if (x > 5)
        min = std::min(min, 1 + arr[x - 5]);
    if (x > 2)
        min = std::min(min, 1 + arr[x - 2]);
    if (x > 1)
        min = std::min(min, 1 + arr[x - 1]);
    return min;
}

不存在整数溢出的问题，因为我在阅读了约束后选择了int数据类型。另外，如果有人想建议我如何删除if梯形图并用更简单的东西替换它，我将非常感谢帮助。另外，感谢您花时间阅读我的问题：）

c++

来源：https://stackoverflow.com/questions/64898373/time-limit-exceeded-on-minimum-coin-change-problemdynamic-programming-implement

2条答案

按热度按时间

c0vxltue1#

#include <iostream>

int main() {
  int tests;
  std::cin >> tests;

  int value;
  while (tests--) {
    int coinCount = 0;
    std::cin >> value;
    while (value > 0) {
      if (value >= 100) {
        coinCount += (value / 100);
        value %= 100;
      } else if (value >= 50) {
        coinCount += (value / 50);
        value %= 50;
      } else if (value >= 10) {
        coinCount += (value / 10);
        value %= 10;
      } else if (value >= 5) {
        coinCount += (value / 5);
        value %= 5;
      } else if (value >= 2) {
        coinCount += (value / 2);
        value %= 2;
      } else if (value >= 1) {
        coinCount += (value / 1);
        value = 0;
      }
    }
    std::cout << coinCount << '\n';
  }
}

在CodeChef上测试并通过，执行时间为0.00。问题中显示的货币系统的设计方式是贪婪的选择是正确的选择。这几乎适用于所有现有的货币系统。
如果你需要证明，http://www.cs.toronto.edu/~denisp/csc373/docs/greedy-coin-change.pdf

赞(0）回复(0）举报 2023-04-01

hfwmuf9z2#

我的简单解决方案：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    vector <int>v{100, 20, 10, 5, 1};
    // vector <int>v{1, 5, 10, 20,  100};
    int n;
    while (cin >> n)
    {
        int mSum(0);
        for (int i:v)
        {
            if (n >= i)
            {
                mSum += n / i;
                n %= i;
            }
        }
        cout << mSum << endl;
    }
    return 0;
}

赞(0）回复(0）举报 2023-04-01

我来回答

c++ CodeChef和CodeForces上的最小硬币变化问题(动态编程实现)超过时间限制

2条答案

相关问题

热门标签

最新问答