[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;
}