做网站有名的公司,深圳创新投资公司官网,太仓公司网站建设电话,开发一款app软件需要多少钱算法学习05#xff1a;离散化、区间合并 文章目录 算法学习05#xff1a;离散化、区间合并前言需要记忆的模版#xff1a;一、离散化1.例题#xff1a;离散化 区间和#xff1a;拓展: 二、区间合并#xff08;贪心#xff09;1.例题#xff1a; 总结 前言 需要记忆的模…算法学习05离散化、区间合并 文章目录 算法学习05离散化、区间合并前言需要记忆的模版一、离散化1.例题离散化 区间和拓展: 二、区间合并贪心1.例题 总结 前言 需要记忆的模版
vectorint alls;//存储所有待离散化的值
sort(alls.begin(), alls.end());//将所有值排序
//去除重复的元素并且不重复的元素 有序 的排在前面
alls.erase(unique(alls.begin(), alls.end()), alls.end()); //找到有序的排在前面的 坐标 所对应的 索引
//返回 坐标 所对应的 映射
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;//索引从0开始映射后从1开始 } //区间合并
void merge(vectorPII segs)
{vectorPII res;//按照 区间左端点 排序 sort(segs.begin(), segs.end());int st -2e9, ed -2e9;//for(auto seg : segs){if(ed seg.first){//一个区间已经合并完了 if(st ! -2e9) res.push_back({st, ed});st seg.first, ed seg.second;//更新 }else ed max(ed, seg.second());//判断 ed 是否要更新 }//注意无论是那种情况到最后都还剩下一个 区间 没有加入到res中 if(st ! -2e9) res.push_back({st, ed}); segs res;
}提示以下是本篇文章正文内容
一、离散化
1.例题离散化 区间和 例题求区间和区间长度无限长无限长的数轴 具体题目假定有一个无限长的数轴数轴上的每个坐标都是0我们首先进行n次操作每次操作将某一位置x上的数加c。 接下来进行m次询问每次询问包含 l 和 r 求区间[lr]间所有数的和。 int main()
{cin n m;//插入n次数操作 --------- 先将数据存储起来 for(int i 0; i n; i ){int x, c;cin x c;add.push_back({x, c});alls.push_back(x);//存储所有待 离散化 的值 }//执行m次询问 --------- 先将数据存储起来 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] a[i] s[i - 1];//处理询问for(auto item : query){int l find(query.first()), r find(query.second());cout s[r] - s[l - 1] endl;} return 0;} 拓展: //------ 拓展 ---------//注意 vectorint :: iterator 与 return a.begin() j;//迭代器 与 索引的关系不清楚。 vectorint :: iterator unique(vectorint a){int j 0;for(int i 0; i a.size(); i ) if(!i a[i] ! a[i - 1]) a[j ] a[i];return a.begin() j;} 二、区间合并贪心
1.例题 例题给n个区间合并有交集的区间求最后剩下的区间个数。 具体题目给定n个区间[l i, r i]要求合并所有有交集的区间注意如果在端点出相交也算有交集最后输出合并完成后的区间个数。 #include iostream
#include vector
#include algorithmusing namespace std;typedef pairint , int PII;const int N 100000 10;int n;
vectorPII segs;//存储合并完后的区间void merge(vectorPII segs)
{vectorPII res;//按照 区间左端点 排序 sort(segs.begin(), segs.end());int st -2e9, ed -2e9;//for(auto seg : segs){if(ed seg.first){if(st ! -2e9) res.push_back({st, ed});//一个区间已经合并完了 st seg.first, ed seg.second;//更新 }else ed max(ed, seg.second());//判断 ed 是否要更新 }//注意无论是那种情况到最后都还剩下一个 区间 没有加入到res中 if(st ! -2e9) res.push_back({st, ed}); segs res;
}int main()
{cin n;for(int i 0; i n; i ){int l, r;cin l r;segs.push_back({l, r});}merge(segs);cout segs.size() endl;return 0;} 总结
提示这里对文章进行总结
