一、离散化的含义:
对于数组a[]={1,3,100,2000,500000,......},把他们一一映射到下标0,1,2,3,4,......的过程叫做离散化
注意:
- a[]中可能有重复元素 ,需要去重如何算出x离散化后的值:二分
二、离散化的过程
vector::erase()的用法:从vector中删除一个元素,参数为要删除元素的位置
vector::erase(first,last)的用法:从vector中删除范围在[first,last)中的元素(不包含last)
vector::unique(first,last)的用法:在[first,last)范围内(不包含last)判断当前元素是否等于上一个元素,将不重复的元素移到前面来(不是将重复的元素移到后面去);需要去重的容器必须是经过排序的有序容器
vector::unique(first,last,pred)的用法:参数pred可以自定义地判断重复的方式
vectora; //存储所有待离散化的值 sort(a.begin(), a.end()); //排序 a.erase(unique(a.begin(), a.end()), a.end()); //去重 // 二分求出x对应的离散化的值 int find(int x) // 找到第一个大于等于x的位置 { int l = 0, r = a.size() - 1; while (l < r) { int mid = l + r >> 1; if (alls[mid] >= x) r = mid; else l = mid + 1; } return r + 1; // 映射到1, 2, ...n;如果是返回r,则为映射到0,1,2,...n }
三、配套练习
AcWing802https://www.acwing.com/problem/content/804/
std::pair(class1,class2) name 的用法:在创建pair对象时,必须提供两个类型名,两个对应的类型名的类型不必相同;pair是将2个数据组合成一组数据,当需要这样的需求时就可以使用pair;另一个应用是,当一个函数需要返回2个数据的时候,可以选择pair; pair的实现是一个结构体,主要的两个成员变量是first,second,这两个值可以分别用pair的两个公有函数first和second访问
使用sort对pair结构进行排序时,sort优先按照变量first排序,然后根据second排序
C++特性:基于范围的for循环:for (dataType rangeVariable : array)
dataType:是范围变量的数据类型。它必须与数组元素的数据类型一样,或者是数组元素可以自动转换过来的类型。rangeVariable:是范围变量的名称。该变量将在循环迭代期间接收不同数组元素的值。在第一次循环迭代期间,它接收的是第一个元素的值;在第二次循环迭代期间,它接收的是第二个元素的值;以此类推。array:是要让该循环进行处理的数组的名称。该循环将对数组中的每个元素迭代一次。
#include#include #include using namespace std; typedef pair PII; const int N = 300010; int n, m; int a[N], s[N]; vector alls; vector add, query; 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() { cin >> n >> m; for (int i = 0; i < n; i ++ ) { int x, c; cin >> x >> c; add.push_back({x, c}); alls.push_back(x); } for (int i = 0; i < m; i ++ ) { int l, r; cin >> l >> r; query.push_back({l, r}); alls.push_back(l); alls.push_back(r); } // 去重 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 处理插入 for (auto item : add) { int x = find(item.first); a[x] += item.second; } // 预处理前缀和 for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i]; // 处理询问 for (auto item : query) { int l = find(item.first), r = find(item.second); cout << s[r] - s[l - 1] << endl; } return 0; } //链接:https://www.acwing.com/activity/content/code/content/40105/
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)