[Algorithm][综合训练][比那名居的桃子][chika和蜜柑][礼物的最大价值]详细讲解

---

1.比那名居的桃子

1.题目链接

• 比那名居的桃子

---

2.算法原理详解 && 代码实现

• 自己的版本：暴力解法 --> 超时 37.5%

  #include <iostream>
  #include <vector>
  using namespace std;int main()
  {int n = 0, k = 0;cin >> n >> k;vector<int> happy(n, 0), shame(n, 0);for(int i = 0; i < n; i++){cin >> happy[i];}for(int i = 0; i < n; i++){cin >> shame[i];}vector<vector<int>> ret(n, vector<int>(2, 0));for(int i = 0; i < n; i++) // 枚举每个起点{for(int j = 0; j < k; j++){if(i + j < n){ret[i][0] += happy[i + j];ret[i][1] += shame[i + j];}}}int day = 0, happyMax = 0;for(int i = 0; i < n; i++){// 目标是：尽可能多的快乐值if(happyMax < ret[i][0]){happyMax = ret[i][0];day = i;}// 快乐值相等 -->  尽可能少的羞耻度if(happyMax == ret[i][0]){if(ret[i][1] < ret[day][1]){day = i;}}// 快乐值 == 羞耻度 -->  尽可能早的吃桃子// 不更新值就可以}cout << day + 1<< endl;return 0;
  }
  

• 优化版本1：滑动窗口

  #include <iostream>
  #include <vector>
  using namespace std;int main()
  {int n = 0, k = 0;cin >> n >> k;vector<int> happy(n, 0), shame(n, 0);for(int i = 0; i < n; i++){cin >> happy[i];}for(int i = 0; i < n; i++){cin >> shame[i];}int left = 0, right = 0;long long hSum = 0, sSum = 0, hMax = 0, sMin = 0, begin = 0;while(right < n){hSum += happy[right];sSum += shame[right];while(right - left + 1 > k){hSum -= happy[left];sSum -= shame[left];left++;}if(right - left + 1 == k){if(hSum > hMax){begin = left;hMax = hSum;sMin = sSum;}else if(hSum == hMax && sSum < sMin){                begin = left;sMin = sSum;}}right++;}cout << begin + 1<< endl;return 0;
  }
  

• 优化版本2：前缀和

---

2.chika和蜜柑

1.题目链接

• chika和蜜柑

---

2.算法原理详解 && 详细讲解

• 优化版本：排序/TOP-K --> 堆/数组模拟均可 --> 自定排序规则

  #include <iostream>
  #include <algorithm>
  #include <vector>
  using namespace std;typedef pair<int, int> PII;int main()
  {int n = 0, k = 0;cin >> n >> k;vector<PII> orgs(n); // <sour, sweet>for(int i = 0; i < n; i++){cin >> orgs[i].first;}for(int i = 0; i < n; i++){cin >> orgs[i].second;}sort(orgs.begin(), orgs.end(), [&](const PII& p1, const PII& p2){if(p1.second != p2.second){return p1.second > p2.second;}else{return p1.first < p2.first;}});long long sour = 0, sweet = 0;for(int i = 0; i < k; i++){sour += orgs[i].first;sweet += orgs[i].second;}cout << sour << " " << sweet << endl;return 0;
  }
  

---

3.礼物的最大价值

1.题目链接

• 礼物的最大价值

---

2.算法原理详解 && 代码实现

• 自己的版本：暴搜 --> 超时

  class Solution 
  {
  public:int dx[2] = {1, 0}; int dy[2] = {0, 1};int n = 0, m = 0, cnt = 0, ret = 0;int maxValue(vector<vector<int> >& grid) {n = grid.size(), m = grid[0].size();DFS(grid, grid[0][0], 0, 0);return ret;}void DFS(vector<vector<int> >& grid, int cnt, int x, int y){if(x == n - 1 && y == m - 1){ret = max(cnt, ret);}for(int k = 0; k < 2; k++){int a = x + dx[k], b = y + dy[k];if(a < n && b < m){DFS(grid, cnt + grid[a][b], a, b);}}}
  };
  

• 优化版本：动态规划 – 路径问题

  int maxValue(vector<vector<int> >& grid)
  {int n = grid.size(), m = grid[0].size();vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));for(int i = 1; i <=n; i++){for(int j = 1; j <= m; j++){dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];}}return dp[n][m];
  }