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

 学习编程就得循环渐进，踏实底子，勿在浮沙筑高台  

 循环渐进Forward-CSDN博客

目录
游游的水果大礼包
 思绪
代码实现：
买卖股票的最好时机(二)
思绪：
代码实现：
倒置字符串
思绪：
代码实现：
游游的水果大礼包

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

   思绪

面对这样一个问题——给定一定命目标苹果和桃子，以及两种不同价值组合方式的礼包（一号礼包和二号礼包），目标是最大化所能组成的礼包总价值。这个问题不能简单地通过贪婪算法解决，因为不同礼包的价值和所需资源比例可能不同，导致无法直接选择价值最高的礼包无限制地组合。
因此，需要接纳一种更全面的搜刮计谋，即摆列法（也称为蛮力法）。这种方法的核心思想是尝试所有可能的礼包组合方式，并记载其中总价值最高的组合。详细步骤如下：

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

这种方法固然直观且可以或许找到最优解，但其时间复杂度较高，特别是在苹果和桃子的数目以及礼包种类较多时。然而，在没有更高效的算法可以利用问题特定结构的情况下，摆列法是一个可靠的选择。
代码实现：

1. #include <iostream>
2. using namespace std;
3. long long n, m, a, b;
4. int main()
5. {
6.     cin >> n >> m >> a >> b;
7.     long long ret = 0;
8.     for(long long x = 0;x <= min(n/2,m);x++)
9.     {
10.         long long y = min(n-x*2,(m-x)/2);
11.         ret = max(ret,a*x+b*y);
12.     }
13.     cout << ret << endl;
14.      return 0;
15. }

复制代码

---

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

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

  思绪：

        典型的动态规划题目，
        dp：每一天的状态有两种，一种是买入，一种是卖出。对于买入来说又有两种： 一种昨天就是买入状态，本日不卖出还是买入状态；另一种是昨天是卖出状态，本日就可以重新买入。对于卖出也是一样的： 一种昨天就是卖出状态，本日不买入还是卖出状态；另一种是昨天是买入状态，本日就可以进行卖出。这样有两个状态的，可以用两个数组来分别表示，并且状态转移方式根据上面的变革也可以很容易的写出。
代码实现：

1. #include <iostream>
2. using namespace std;
3. #include <vector>
4. int main() {
5.     int n;
6.     cin >> n;
7.     vector<int> nums(n);
8.     for (int i = 0; i < n; i++)
9.         cin >> nums[i];
10.         
11.     vector<int> f(n), g(n);
12.     f[0] = -nums[0];
13.     for (int i = 1; i < n; i++)
14.     {
15.         f[i] = max(f[i - 1], g[i - 1] - nums[i]);
16.         g[i] = max(g[i - 1], f[i - 1] + nums[i]);
17.     }
18.     cout << g[n - 1];
19.     return 0;
20. }

复制代码

---

倒置字符串

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

  思绪：

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

1. #include <iostream>
2. using namespace std;
3. #include <string>
4. void Reverse(string& s, int left, int right)
5. {
6.     while (left < right)
7.     {
8.         swap(s[left++], s[right--]);
9.     }
10. }
11. int main()
12. {
13.     string s;
14.     getline(cin, s);
15.     Reverse(s, 0, s.size() - 1);
16.     int left = 0, right = 0;
17.     while (right < s.size())
18.     {
19.         while (right < s.size() && s[right] != ' ') right++;
20.         Reverse(s, left, right - 1);
21.         left = right + 1;
22.         right = left;
23.     }
24.     cout << s;
25.     return 0;
26. }

复制代码

---

  学习编程就得循环渐进，踏实底子，勿在浮沙筑高台

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。