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.题目链接
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]; }