基本算法——离散化
概念
离散化,把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。步骤:
通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小。
【基本算法——离散化】1.将所有需要离散化的数据(如下面例子中的下标)放到一个容器中(以下使用vector,当然可以用数组代替);举例 模板题链接:区间和
2.排序,去重(可以手写,也可以用STL的algorithm库中的unique函数);
3.要查询原数据在容器中的位置只需在容器中二分查找第一个大于等于该数据的数的位置即可。
代码如下:
#include#include #include using namespace std; const int N = 100010; vector alls; int n, m; int x[N], c[N], l[N], r[N]; int a[N * 3], s[N * 3]; // 找到x在alls中的下标 int find(int x) { int l = 0, r = alls.size() - 1; while (l < r) { int mid = l + r >> 1; if (alls[mid] >= x) r = mid; else l = mid + 1; } return r + 1; }int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++ ) { scanf("%d%d", &x[i], &c[i]); alls.push_back(x[i]); } for (int i = 0; i < m; i ++ ) { scanf("%d%d", &l[i], &r[i]); alls.push_back(l[i]), alls.push_back(r[i]); }// 排序 + 判重 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 插入操作 for (int i = 0; i < n; i ++ ) a[find(x[i])] += c[i]; // 预处理前缀和 for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i]; // 查询操作 for (int i = 0; i < m; i ++ ) printf("%d\n", s[find(r[i])] - s[find(l[i]) - 1]); return 0; }
推荐习题:赶牛入圈(POJ3179)
转载于:https://www.cnblogs.com/ninedream/p/11241165.html
推荐阅读
- 基础算法模板总结|离散化 算法 思路+模板代码
- 算法板子|二分法详解
- 算法小结|基础算法——离散化
- 数据结构|离散化算法
- 决策树|决策树,随机森林,集成学习的算法实现
- 机器学习与数据挖掘|一文读懂常用机器学习解释性算法(特征权重,feature_importance, lime,shap)
- Vite 源码解读系列(图文结合) —— 插件篇
- 算法|学会二叉树不知道干啥?二叉树的深度优先搜索和广度优先搜索,我要打十个乃至二十个(打开你的LeetCode撸起来)学练并举
- C语言|C语言初阶学习——扫雷小游戏(递归)
- C语言|C语言初阶学习——三字棋入门小游戏(超详解)