離散化
離散化，把無限空間中有限的個體映射到有限的空間中去，以此提高演算法的時空效率，
通俗的說，離散化是在不改變資料相對大小的條件下，對資料進行相應的縮小，例如：
原資料：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.二分函式第三個引數要是一個結構體
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/277116.html
標籤：其他
下一篇：關于C語言記憶體溢位風險