[Algorithm][综合训练][栈和排序][加减]详细讲解

本文主要是介绍[Algorithm][综合训练][栈和排序][加减]详细讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.栈和排序

1.题目链接

栈和排序

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

解法：栈 + 贪心 -> 每次尽可能先让当前需要的最大值弹出去

vector<int> solve(vector<int>& a) 
{int n = a.size();vector<bool> hash(n + 1, false);vector<int> ret;int aim = n;stack<int> st;for(auto& x : a){st.push(x);hash[x] = true;// 先更新目标值while(hash[aim]){aim--;}// 出栈while(st.size() && st.top() >= aim){ret.push_back(st.top());st.pop();}}return ret;
}

2.加减

1.题目链接

加减

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

解法：枚举 + 前缀和 + 滑动窗口 + 贪心

贪心：尽可能选择一些挨得比较近的数，让他们变成相同的数
- 排序
枚举：枚举所有的区间，找出区间内所有数变成相同的数的最小代价(cost <= k)的最大区间
如何求一个区间的最小代价cost?
- 数学问题：数轴上有一些点，选取一个位置，使所有点到它的距离之和最小
- 结论：选择最中间的点 -> 奇数点时就是中间，偶数点时，中间的两个随意哪个都可以
优化一：前缀和优化求最小代价cost
优化二：滑动窗口优化枚举所有区间

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;vector<long long> nums, sum;long long Cal(int l, int r)
{int mid = (l + r) / 2;return (mid - l - r + mid) * nums[mid] - (sum[mid - 1] - sum[l - 1]) + (sum[r] - sum[mid]);
}int main()
{long long n = 0, k = 0;cin >> n >> k;nums.resize(n + 1, 0);sum.resize(n + 1, 0);for(int i = 1; i <= n; i++){cin >> nums[i];}sort(nums.begin() + 1, nums.end());// 初始化前缀和数组for(int i = 1; i <= n; i++){sum[i] = sum[i - 1] + nums[i];}int left = 1, right = 1, ret = 1;while(right <= n){long long cost = Cal(left, right);while(cost > k){left++;cost = Cal(left, right);}ret = max(ret, right - left + 1);right++;}cout << ret << endl;return 0;
}