【C++笔试强训】如何成为算法糕手Day11

小文要打代码

发布于 2024-10-20 08:45:22

670

发布于 2024-10-20 08:45:22

文章被收录于专栏：C++学习历程

学习编程就得循环渐进，扎实基础，勿在浮沙筑高台

游游的水果大礼包

牛客网做题链接：游游的水果大礼包 (nowcoder.com)

思路

面对这样一个问题——给定一定数量的苹果和桃子，以及两种不同价值组合方式的礼包（一号礼包和二号礼包），目标是最大化所能组成的礼包总价值。这个问题不能简单地通过贪心算法解决，因为不同礼包的价值和所需资源比例可能不同，导致无法直接选择价值最高的礼包无限制地组合。

因此，需要采取一种更全面的搜索策略，即枚举法（也称为蛮力法）。这种方法的核心思想是尝试所有可能的礼包组合方式，并记录其中总价值最高的组合。具体步骤如下：

初始化：设定一个变量来记录当前找到的最大总价值。
枚举过程：
- 从一号礼包选择0个开始，逐渐增加一号礼包的数量，同时相应地减少二号礼包的数量，以保持苹果和桃子的总数不变。
- 对于每一种一号礼包和二号礼包的组合数量，计算当前组合的总价值。
- 如果当前组合的总价值大于之前记录的最大总价值，则更新最大总价值。
结束条件：当一号礼包的数量增加到无法再增加（即使用了所有可用的苹果和桃子），或者二号礼包的数量减少到0时，枚举过程结束。
返回结果：返回记录的最大总价值。

这种方法虽然直观且能够找到最优解，但其时间复杂度较高，特别是在苹果和桃子的数量以及礼包种类较多时。然而，在没有更高效的算法可以利用问题特定结构的情况下，枚举法是一个可靠的选择。

代码实现：

#include <iostream>
using namespace std;
long long n, m, a, b;
int main()
{ 
    cin >> n >> m >> a >> b;
    long long ret = 0;
    for(long long x = 0;x <= min(n/2,m);x++)
    {
        long long y = min(n-x*2,(m-x)/2);
        ret = max(ret,a*x+b*y);
    }
    cout << ret << endl;
     return 0;
}

买卖股票的最好时机(二)

牛客网做题链接：买卖股票的最好时机(二)_牛客题霸_牛客网 (nowcoder.com)

思路：

典型的动态规划题目，

dp：每一天的状态有两种，一种是买入，一种是卖出。对于买入来说又有两种：一种昨天就是买入状态，今天不卖出还是买入状态；另一种是昨天是卖出状态，今天就可以重新买入。对于卖出也是一样的：一种昨天就是卖出状态，今天不买入还是卖出状态；另一种是昨天是买入状态，今天就可以进行卖出。这样有两个状态的，可以用两个数组来分别表示，并且状态转移方式根据上面的变化也可以很容易的写出。

代码实现：

#include <iostream>
using namespace std;
#include <vector>
int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++)
        cin >> nums[i];
        
    vector<int> f(n), g(n);
    f[0] = -nums[0];
    for (int i = 1; i < n; i++) 
    {
        f[i] = max(f[i - 1], g[i - 1] - nums[i]);
        g[i] = max(g[i - 1], f[i - 1] + nums[i]);
    }
    cout << g[n - 1];
    return 0;
}

倒置字符串

牛客网做题链接：倒置字符串_牛客题霸_牛客网 (nowcoder.com)

思路：

不调用C++库函数reverse，将整串字符串逆置6，再将每个单词进行逆置

代码实现：

#include <iostream>
using namespace std;
#include <string>
void Reverse(string& s, int left, int right) 
{
    while (left < right) 
    {
        swap(s[left++], s[right--]);
    }
}
int main() 
{
    string s;
    getline(cin, s);
    Reverse(s, 0, s.size() - 1);
    int left = 0, right = 0;
    while (right < s.size()) 
    {
        while (right < s.size() && s[right] != ' ') right++;
        Reverse(s, left, right - 1);
        left = right + 1;
        right = left;
    }
    cout << s;
    return 0;
}

学习编程就得循环渐进，扎实基础，勿在浮沙筑高台

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-19，如有侵权请联系 cloudcommunity@tencent.com 删除

字符串