二分查找技巧—位元組跳動2018校招算法方向(第二批)—用戶喜好

[編程題]用戶喜好

時間限制:3秒

空間限制:262144K

為了不斷優化推薦效果,今日頭條每天要存儲和處理海量數據。假設有這樣一種場景:我們對用戶按照它們的註冊時間先後來標號,對於一類文章,每個用戶都有不同的喜好值,我們會想知道某一段時間內註冊的用戶(標號相連的一批用戶)中,有多少用戶對這類文章喜好值為k。因為一些特殊的原因,不會出現一個查詢的用戶區間完全覆蓋另一個查詢的用戶區間(不存在L1<=L2<=R2<=R1)。

輸入描述:
輸入: 第1行為n代表用戶的個數 第2行為n個整數,第i個代表用戶標號為i的用戶對某類文章的喜好度 第3行為一個正整數q代表查詢的組數  第4行到第(3+q)行,每行包含3個整數l,r,k代表一組查詢,即標號為l<=i<=r的用戶中對這類文章喜好值為k的用戶的個數。 數據範圍n <= 300000,q<=300000 k是整型
輸出描述:
輸出:一共q行,每行一個整數代表喜好值為k的用戶的個數
輸入例子1:
5  1 2 3 3 5  3  1 2 1  2 4 5  3 5 3
輸出例子1:
1  0  2
例子說明1:
樣例解釋:  有5個用戶,喜好值為分別為1、2、3、3、5,  第一組詢問對於標號[1,2]的用戶喜好值為1的用戶的個數是1  第二組詢問對於標號[2,4]的用戶喜好值為5的用戶的個數是0  第三組詢問對於標號[3,5]的用戶喜好值為3的用戶的個數是2

解題思路:
剛開始看到題目,覺得是區間查詢的題目,於是想線段樹、RMQ那些,結果發現查找的k值不能預先存為狀態。搜了一下題解發現只是用到二分查找的技巧,看看下圖就明白了:

 

 

 為了進行二分查找,我們對喜好值進行排序,但是注意到有查詢區間,所以標號也必須一起排序。需要注意的是在喜好值相等的片段里標號也要排成遞增次序,這個可以寫個結構體(記為Num)然後重寫比較函數。那麼在標號按遞增次序後,我們可以發現,如果要查找[2,6]區間里喜好值為2的人數,只需要二分查找k=2,L=2的上界,以及k=2,R=6的下界。

(也可以理解為先二分查找k所在的區間,然後二分查找L和R的位置,然後取其長度,但實際上只需要兩次二分查找就行了,畢竟排序函數如果可以用比較函數把數組排好序,那麼同樣可以只用一次二分查找把邊界找出來,因為它們都用到自定義的比較函數)

如圖找到下界4和上界6,那麼上界與下界之間的長度即為[2,6]之間的喜好值為2的人數。

 

需要用到的是二分查找的函數,這裡複習一下:

lower_bound找到第一個大於或等於左端點的位置,

upper_bound找到最後一個小於或等於右端點的位置

 1 #include<iostream>   2 #include<cstdio>   3 #include<algorithm>   4 using namespace std;   5   6 const int maxn=300000+5;   7   8 struct Num{   9     int id;  10     int val;  11      bool operator<(const Num &b)const{  12         if(val==b.val)return id<b.id;  13         else return val<b.val;  14     }  15 }num[maxn];  16  17 int main()  18 {  19     int n;  20     scanf("%d",&n);  21     for(int i=0;i<n;i++){  22         scanf("%d",&num[i].val);  23         num[i].id=i;  24     }  25     sort(num,num+n);  26     int q;  27     scanf("%d",&q);  28     while(q--){  29         int l,r,k;  30         scanf("%d%d%d",&l,&r,&k);  31         l--; r--;  32         Num L,R;  33         L.id=l;   R.id=r;  34         L.val=R.val=k;  35         int ansL=lower_bound(num,num+n,L)-num;  36         int ansR=upper_bound(num,num+n,R)-num;  37         printf("%dn",ansR-ansL);  38     }  39  40     return 0;  41 }