此期限为一秒。对于某些未知的测试用例,我的程序需要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;
}
这里是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。这些代码高尔夫练习可能很有趣,但是它们却无助于教最佳实践甚至您在做什么。它们通常只是对模式查找(这可能是有益的)和死记硬背某些算法(不太好)的测试。