我如何优化这段C ++代码?

问题描述 投票:-2回答:1

此期限为一秒。对于某些未知的测试用例,我的程序需要1.01s的时间。问题是

您正在开发智能手机应用。您有您的应用程序的潜在客户列表。每个客户都有预算,并且仅当价格小于或等于客户预算时,才会以您声明的价格购买该应用程序。

您想确定价格,以使从应用程序中获得的收入最大化。找到最大可能的收入。

例如,假设您有4个潜在客户,并且他们的预算分别是30、20、53和14。在这种情况下,您可以获得的最高收入是60。

我确定代码正确无误。我只想优化它。请帮我这样做。我是初学者。

代码:

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

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    int n, x, i, j, k;
    cin >> n;
    vector<int> v;
    for (i = 0; i < n; ++i) 
    {
        cin >> x;
        v.push_back(x);
    }
    int maximum = *max_element(v.begin(), v.end());
    int minimum = *min_element(v.begin(), v.end());
    vector<long long int> sums;
    for (j = minimum; j <= maximum; ++j)
    {
        vector<int> prices;
        for (k = 0; k < n; ++k)
        {
            if (j > v[k]) {
                ;
            } else {
                prices.push_back(j);
            }
        }
        sums.push_back(accumulate(prices.begin(), prices.end(), 0));
        prices.clear();
    }
    long long int maxsum = *max_element(sums.begin(), sums.end());
    cout << maxsum;
}
c++ optimization
1个回答
2
投票

这里是CodeChef的时间为0.19 s的示例。

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

int main() {
  int number;
  std::vector<int> budgets;

  std::cin >> number;

  budgets.resize(number);

  for (std::size_t i = 0; i < budgets.size(); ++i) {
    std::cin >> budgets[i];
  }

  std::sort(budgets.begin(), budgets.end());

  std::size_t max = 0;
  for (std::size_t i = 0; i < budgets.size(); ++i) {
    std::size_t tmp = budgets[i] * (budgets.size() - i);
    if (tmp > max) {
      max = tmp;
    }
  }

  std::cout << max;
}

一旦知道矢量所需的大小,便会调整其大小。这将停止在元素2、4、8等处对向量进行大小调整。调整大小的速度快于> 1。现在,由于已经过调整大小,因此我也可以只对[]使用直接元素访问。 .at()更安全,但会带来异常,并且此练习是为了最大程度地减少运行时间,因此我们不会这样做。

这里的关键是对向量进行排序。在评论中对此进行了解释,但是总体思路是,与未排序的数据相比,排序后的数据处理速度要快得多。排序本身以O(nlogn)时间运行,但是现在我们得到了更快的算法。

新算法依赖于排序的数据。索引0的价格最小,这意味着每个人都可以以该价格买得起。我的收入将是元素0的预算乘以元素数(.size())。当我到达第二个元素时,每个

except

索引为零的人都负担得起,所以我的收入是元素1的预算乘以大小减去一。等等。在计算这些潜在收入时,我将它们与max变量进行了比较。如果我计算更大,则将max替换为新值,否则我将其保留。您会注意到,我不知道实际设定的价格。这不是提交的要求,所以我不在乎。

个人意见时间,像这样的网站非常糟糕,值得学习。您最好先找到一个YouTube系列视频或参加一门课程或getting a good book。这些代码高尔夫练习可能很有趣,但是它们却无助于教最佳实践甚至您在做什么。它们通常只是对模式查找(这可能是有益的)和死记硬背某些算法(不太好)的测试。

© www.soinside.com 2019 - 2024. All rights reserved.