离散化思想(好像都可以用map来解决捏)#
数据离散化是一个非常重要的思想。
为什么要离散化?当以权值为下标的时候，有时候值太大，存不下。 所以把要离散化的每一个数组里面的数映射到另一个值小一点的数组里面去。
打个比方，某个题目告诉你有1e4个数，每个数大小不超过1e10，要你对这些数进行操作，那么肯定不能直接开1e10大小的数组，但是1e4的范围就完全没问题。
我们来看一下定义：离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。（by百度百科）
通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：
原数据：1,999,100000,15；处理后：1,3,4,2；
原数据：{100,200}，{20,50000}，{1,400}；
处理后：{3,4}，{2,6}，{1,5}；
但是离散化仅适用于只关注元素之间的大小关系而不关注元素本身的值!
假如你想写的更加专业就要采用以下步骤：
1、排序
2、去重
3、索引
首先我们要对所要进行离散化的数据进行排序：一般使用sort对数组或结构体排序。
然后是去重操作，为了写出高效的代码，我们需要复习两个STL函数：unique（）和lower_bound（），他们同时隶属于#include。
unique的作用是“去掉”容器中相邻元素的重复元素（不一定要求数组有序），它会把重复的元素添加到容器末尾（所以数组大小并没有改变），而返回值是去重之后的尾地址；
函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置。【ps.upper_bound是返回第一个大于b[x]的指针，upper_bound（）=lower_bound（）+1】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于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; // 映射到1, 2, ...n
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
vector<PII> add , query;
vector<int> alls; // 储存大区间内所有出现过的数
int a[300010] , s[300010];
int find(int x){
int pos;
pos = lower_bound(alls.begin(),alls.end(),x) - alls.begin() ; //查询集中起来后的数的下标
return pos+1; //下标从 1 开始;
}
int main()
{
int n,m,x,c;
cin>>n>>m;
while(n--){
cin>>x>>c;
add.push_back({x,c});
alls.push_back(x);
}
while(m--){
cin>>x>>c;
query.push_back({x,c});
alls.push_back(x);
alls.push_back(c);
}
sort(alls.begin(),alls.end()); //由于是坐标，即可以排序去重
alls.erase(unique(alls.begin(), alls.end()) , alls.end()); //在大区间内出现过的数集中排序去重
// unique()把不重复的元素排序放在最前边, 返回这些有序序列最后一个元素的后一个迭代器;
for(auto item : add){
int pos = find(item.first); //查询下标 ,然后累加;
a[pos] += 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);
int r = find(item.second);
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int> st;
const int N = 3*200005;
int a[N],b[N],c[N],ans[N];
vector<int> alls;
int n,m;
int find(int x){
return lower_bound(alls.begin(),alls.end(),x)-alls.begin();
}
int main()
{
cin>>n;
for (int i = 1; i <=n; i ++ ){
cin>>a[i];
alls.push_back(a[i]);
}
cin>>m;
for (int i = 1; i <=m; i ++ ){
cin>>b[i];
alls.push_back(b[i]);
}
for (int i = 1; i <=m; i ++ ){
cin>>c[i];
alls.push_back(c[i]);
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for(int i=1;i<=n;i++) ans[find(a[i])]++;
//遍历所有电影，按要求找到最多科学家会的电影
int ans0,ans1,ans2;
//ans0保存最终结果，ans1和ans2为中间结果
ans0=ans1=ans2=0;
for(int i=1;i<=m;i++){
//算出第i个电影音频语言的科学家数，和第i个字幕语言的科学家数
int anx=ans[find(b[i])],any=ans[find(c[i])];
//如果ans大于ans1或者前者相等且any大于ans2时，更新
if(anx>ans1 || (anx==ans1 && any>ans2)){
ans0=i,ans1=anx,ans2=any;
}
}
if(ans0==0){
printf("%d\n",1);
}else{
printf("%d\n",ans0);
}
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
//2个map也可以
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int> st;
const int N = 200005;
typedef pair<int, int> PII;
unordered_map<int,PII> dd;
PII r[N];
int n,m;
int main()
{
cin>>n;
for (int i = 0; i < n; i ++ ){
int x;
cin>>x;
st[x]++;
}
cin>>m;
for (int i = 0; i < m; i ++ ){
int a;
cin>>a;
r[i].first=st[a];
dd[i].first=st[a];
}
for (int i = 0; i < m; i ++ ){
int a;
cin>>a;
r[i].second=st[a];
dd[i].second=st[a];
}
sort(r,r+m);
for (auto d:dd){
if(d.second==r[m-1]){
cout<<d.first+1<<endl;
break;
}
}
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include<bits/stdc++.h>
using namespace std;
const int N = 2*20005;
int n,x,y,z;
vector<int> alls;
typedef pair<int, int> PII;
PII a[N];
int s[N];
int find(int x){
return lower_bound(alls.begin(),alls.end(),x)-alls.begin()+1;
}
int main()
{
cin>>n>>x>>y>>z;
for(int i =1;i<=n;i++){
cin>>a[i].first>>a[i].second;
alls.push_back(a[i].first);
alls.push_back(a[i].second);
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for(int i =1;i<=n;i++){
int p = find(a[i].first),q=find(a[i].second);
s[0]+=x;
s[p]+=y-x,s[q+1]+=z-y;
}
int cur = 0,res= 0;;
for(int i =1;i<alls.size();i++){
cur+= s[i-1];
if(cur>res){
res=cur;
}
}
cout<<res<<endl;
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include<bits/stdc++.h>
using namespace std;
map<int,int> mp;
int main(){
int n,x,y,z;
scanf("%d%d%d%d",&n,&x,&y,&z);
int l,r;
for(int i=0;i<n;i++){
scanf("%d%d",&l,&r);
mp[0]+=x;
mp[l]=mp[l]-x+y;
mp[r+1]=mp[r+1]-y+z;
}
int mx=0,cur=0;
for(auto iter:mp){
cur+=iter.second;
if(cur>mx){
mx=cur;
}
}
printf("%d\n",mx);
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 1e9+5;
map<int, int> mp;
int main(){
cin>>n;
int a = 0,b;
while(n--){
char c;
cin>>b>>c;
if(c=='R'){
mp[a]++;mp[a+b]--;a=a+b;
}else{
mp[a-b]++;mp[a]--;a=a-b;
}
}
int sum = 0, ans = 0, L;
//前缀和是差分的逆操作，用sum记录当前值，扫描一遍
for(auto [k, v] : mp){
cout<<k<<" "<<v<<endl;
// debug3(k, v, sum);
if(sum <= 1 && sum + v > 1) L = k; //如果sum 从比2小变到比2大，那么k值就是区间左端点
else if(sum > 1 && sum + v <= 1) ans += k - L; //反之就是区间右端点
sum += v;//更新sum 的值
}
cout << ans;
return 0;
}
|
https://www.acwing.com/problem/search/1/?csrfmiddlewaretoken=ZbNNyBOznDdROxrPJ79ujrDB4Y3Ir2uLvIPfZmiggmHF9XvX5jt33nH7kPOAyxIa&search_content=%E7%A6%BB%E6%95%A3%E5%8C%96