[Algorithm][综合训练][删除相邻数字的最大分数][分组][十字爆破]详细讲解

本文主要是介绍[Algorithm][综合训练][删除相邻数字的最大分数][分组][十字爆破]详细讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

1.删除相邻数字的最大分数

1.题目链接

• 删除相邻数字的最大分数

---

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

• 自己的版本：贪心 --> 20% --> 自己知道这个策略必错 --> 而且数据范围没注意到

  #include <iostream>
  #include <queue>
  using namespace std;typedef pair<int, int> PII;struct Compare
  {bool operator()(PII p1, PII p2){return p1.first < p2.first;}
  };int main()
  {int n = 0;cin >> n;int x = 0;int hash[10] = { 0 };while(cin >> x){hash[x] += x;}priority_queue<PII, vector<PII>, Compare> heap;for(int i = 1; i < 10; i++){heap.push({hash[i], i});}int cnt = 0;while(heap.size()){auto [total, x] = heap.top();heap.pop();if(hash[x]){cnt += total;hash[x - 1] = 0, hash[x + 1] = 0;}}cout << cnt << endl;return 0;
  }
  

• 优化版本：动态规划 – 线性dp
  • 状态表示：
    • f[i]：选到i位置时，i位置必选，此时的最大分数
    • g[i]：选到i位置时，i位置不选，此时的最大分数
  • 状态转移方程：
    • f[i] = hash[i] + g[i - 1]
    • g[i] = max(f[i - 1], g[i - 1]

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

---

2.分组

1.题目链接

• 分组

---

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

• 自己的策略：拿着人数，去分组 --> 几乎不可行的策略，指数级的时间复杂度
• 优化版本：枚举 + 二分 --> 枚举最终的分配结果中，最多的人数

  #include <iostream>
  #include <unordered_map>
  using namespace std;int n = 0, m = 0;
  unordered_map<int, int> cnt;// 判断人数最多为x时，能否分成m组
  bool Check(int x)
  {int g = 0;for(auto& [a, b] : cnt){g += b / x + (b % x == 0 ? 0 : 1);}return g <= m;
  }int main()
  {cin >> n >> m;int x = 0, hMax = 0;for(int i = 0; i < n; i++){cin >> x;hMax = max(hMax, ++cnt[x]);}if(cnt.size() > m) // 边界情况处理{cout << -1 << endl;}else{int l = 1, r = hMax;while(l < r){int mid = (l + r) / 2;if(Check(mid)){r = mid;}else{l = mid + 1;}}cout << l << endl;}return 0;
  }
  

---

3.十字爆破

1.题目链接

• 十字爆破

---

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

• 自己的版本：暴力模拟 --> 超时 50%

  #include <iostream>
  #include <vector>
  using namespace std;int n = 0, m = 0;
  vector<vector<int>> nums;long long GetSum(int x, int y)
  {long long ret = 0;for(int i = 0; i < m; i++){ret += nums[x][i];}for(int i = 0; i < n; i++){ret += nums[i][y];}return ret - nums[x][y];
  }int main()
  {cin >> n >> m;nums.resize(n, vector<int>(m, 0));for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){scanf("%d", &nums[i][j]);}}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){printf("%lld ", GetSum(i, j));}printf("\n");}return 0;
  }
  

• 优化版本：预处理 --> 先把每一行以及每一列的和存起来，再去直接拿现成的值

  #include <iostream>
  #include <vector>
  using namespace std;int main()
  {int n = 0, m = 0;scanf("%d %d", &n, &m);vector<vector<int>> nums(n, vector<int>(m, 0));vector<long long> row(n, 0), col(m, 0);for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){scanf("%d", &nums[i][j]);row[i] += nums[i][j];col[j] += nums[i][j];}}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){printf("%lld ", row[i] + col[j] - nums[i][j]);}printf("\n");}return 0;
  }
  

这篇关于[Algorithm][综合训练][删除相邻数字的最大分数][分组][十字爆破]详细讲解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---