基础算法学习－－离散化

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了基础算法学习－－离散化，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2113字，纯文字阅读大概需要4分钟。

内容图文

离散化的概念

题目给出范围很大但数据数量很少的一组数据，通过离散化将大的下标的值赋值给新的较小的连续的下标，从而讲一个范围很大的数据合集装进一个小的容器中。

离散化模板

vecrot<int> alls; // 储存所有待离散化的值

sort(alls.begin(),alls.end()); // 将alls里的所有待离散化的值总小到大排序

alls.erase(unique(alls.begin(),alls.end()),alls.end()) // 将重复的待离散化数据删除
						//因为离散化是下标对下标的映射，不需要重复值。

通过二分求出x（大的下标）对应离散化后的值（小的下标）

int find(int x){
	int l = 0,r = alls.size() - 1;
	while( l < r ){
		int mid = l + r >> 1;
		// 找出第一个>=x的数
		if(alls[mid] >= x) r = mid;
		else l = mid + 1;
	}
	return r + 1; //这样离散化映射的值是从1开始的
}

一题例题

题目

假定有一个无限长的数轴，数轴上每个坐标上的数都是 00。

现在，我们首先进行 nn 次操作，每次操作将某一位置 xx 上的数加 cc。

接下来，进行 mm 次询问，每个询问包含两个整数 ll 和 rr，你需要求出在区间 [l,r][l,r] 之间的所有数的和。

输入格式
第一行包含两个整数 nn 和 mm。

接下来 nn 行，每行包含两个整数 xx 和 cc。

再接下来 mm 行，每行包含两个整数 ll 和 rr。

输出格式
共 mm 行，每行输出一个询问中所求的区间内数字和。

数据范围
?109≤x≤109?109≤x≤109,
1≤n,m≤1051≤n,m≤105,
?109≤l≤r≤109?109≤l≤r≤109,
?10000≤c≤10000

题解

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

const int N = 300010;

typedef pair<int,int> p;

int n,m;
int a[N],s[N];
vector<p> add,query;
vector<int> 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(){
    cin>>n>>m;
    while(n --){
        int x,c;
        cin>>x>>c;
        add.push_back({x,c});
        
        alls.push_back(x);
    }
    
    while(m --){
        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;
}

一些注解

pair 是可以存两个数据的数组.
alls.erase() 擦去指定部分
unique() 将所有重复的数放在最后面并返回end的值

内容总结

以上是互联网集市为您收集整理的基础算法学习－－离散化全部内容，希望文章能够帮你解决基础算法学习－－离散化所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---