离散化
离散化,把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。
通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小。例如:
原数据:1,999,100000,15;处理后:1,3,4,2;
原数据:{100,200},{20,50000},{1,400};
处理后:{3,4},{2,6},{1,5};
Gym 101964E Fishermen
题意:
求每个渔民的鱼竿能钓到多少鱼,渔民都在x轴上,且每个渔民位置一定不同,在其他点上有鱼(一个点可能有好几条鱼),若渔民坐标(x,0),鱼坐标(a,b),鱼竿长为l,当且仅当满足 |a ? x| + b <= l时,这条鱼能被渔夫捕到.
分析:
求每条鱼对渔民的贡献,据鱼的坐标我们可以求出,有哪几个渔夫可以捕到这条鱼,对这些渔夫能捕的鱼加1,由于这些渔夫一定是连续的,相当于对一个区间加一,我们可以利用差分,最后跑一边前缀和即可求出在每个点上人能捕到的鱼。
但是,据数据范围渔夫坐标最大1e9,然而渔夫总是只有2e5,所以,我们考虑离散化。
AC代码:
#include <bits/stdc++.h>
using namespace std;
int n, m, l;
int x[200050], y[200050];
int d[200050];
int ans[200050];
int ar[200050];
int le, ri;
struct node
{
int x, id;
bool operator < (const node &b) const
{
return x < b.x;
}
}br[200050];
node xx;
int main()
{
scanf("%d%d%d", &n, &m, &l);
for(int i = 1; i <= n; ++i) scanf("%d%d", &x[i], &y[i]);
for(int i = 1; i <= m; ++i)
{
scanf("%d", &ar[i]);
br[i].x = ar[i];
br[i].id = i;
}
sort(br + 1, br + m + 1);
for(int i = 1; i <= n; ++i)
{
if(y[i] > l) continue;
xx.x = x[i] - (l - y[i]);
le = lower_bound(br + 1, br + m + 1, xx) - br;
if(le > m) continue;
xx.x = x[i] + (l - y[i]);
ri = upper_bound(br + 1, br + m + 1, xx) - br;
++d[le];
--d[ri];
}
for(int i = 1; i <= m; ++i)
{
d[i] += d[i - 1];
ans[br[i].id] = d[i];
}
for(int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
return 0;
}
/*
8 4 4
7 2
3 3
4 5
5 1
2 2
1 4
8 4
9 4
6 1 4 9
*/
在结构体里二分查找
1.写operator
2.二分函数第三个参数要是一个结构体