#include<iostream>#include<vector>usingnamespace std;intmain(){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;return0;}
优化版本1:滑动窗口
#include<iostream>#include<vector>usingnamespace std;intmain(){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;longlong 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;}elseif(hSum == hMax && sSum < sMin){ begin = left;sMin = sSum;}}right++;}cout << begin +1<< endl;return0;}
优化版本2:前缀和
2.chika和蜜柑
1.题目链接
chika和蜜柑
2.算法原理详解 && 详细讲解
优化版本:排序/TOP-K --> 堆/数组模拟均可 --> 自定排序规则
#include<iostream>#include<algorithm>#include<vector>usingnamespace std;typedef pair<int,int> PII;intmain(){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;}});longlong sour =0, sweet =0;for(int i =0; i < k; i++){sour += orgs[i].first;sweet += orgs[i].second;}cout << sour <<" "<< sweet << endl;return0;}
3.礼物的最大价值
1.题目链接
礼物的最大价值
2.算法原理详解 && 代码实现
自己的版本:暴搜 --> 超时
classSolution{public:int dx[2]={1,0};int dy[2]={0,1};int n =0, m =0, cnt =0, ret =0;intmaxValue(vector<vector<int>>& grid){n = grid.size(), m = grid[0].size();DFS(grid, grid[0][0],0,0);return ret;}voidDFS(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);}}}};
优化版本:动态规划 – 路径问题
intmaxValue(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];}