[演算法心得] Codefoces. Binary Search

jimmyhealer

嗨大家好~ 我是新加入論壇的萌新，之後可能會每日更新一下演算法心得，那目前會在 c/c++ 版，如果大家很熱絡的話再申請 演算法/競賽程式 版吧!

--------------------------------------------------- 正文開始 ---------------------------------------------------

題目名稱: Binary Search
題目網站: Codefoces
題目網址: https://codeforces.com/problemset/problem/1436/C
題目內容:

Andrey thinks he is truly a successful developer, but in reality he didn't know about the binary search algorithm until recently. After reading some literature Andrey understood that this algorithm allows to quickly find a certain number x in an array. For an array a indexed from zero, and an integer x the pseudocode of the algorithm is as follows:

Note that the elements of the array are indexed from zero, and the division is done in integers (rounding down).

Andrey read that the algorithm only works if the array is sorted. However, he found this statement untrue, because there certainly exist unsorted arrays for which the algorithm find x!

Andrey wants to write a letter to the book authors, but before doing that he must consider the permutations of size n such that the algorithm finds x in them. A permutation of size n is an array consisting of n distinct integers between 1 and n in arbitrary order.

Help Andrey and find the number of permutations of size n which contain x at position pos and for which the given implementation of the binary search algorithm finds x (returns true). As the result may be extremely large, print the remainder of its division by 10^9+7.

題目大意:

給你三個數字 n, x, pos，分別代表陣列長度、要尋找的數、以及那個數位置。
問你陣列有多少種排列，可以使 binary_search return true。

範例輸入 #1:
4 1 2

範例輸出 #1:
6

範例輸入 #2:
123 42 24

範例輸出 #2:
824071958

--------------------------------------------------- 題解心得 ---------------------------------------------------


可以先觀察 binary_search 的演算法，每次可以 mid 與下一個值的大小關係，最後確定目標位置左右大小數量。
陣列可以設為 [左邊空格] [目標] [右邊空格]。
所以就會總結出公式 C(左邊空格, 左邊小於目標的數字) * C(右邊空格, 右邊大於目標的數字) 。

1. #include<bits/stdc++.h>
   
2. #define ll long long
   
3. #define INF 0x3f3f3f3f
   
4. #define MOD 1000000007
   
5. #define io iOS::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   
6. using namespace std;
   
7. const int MXN = 10;
   
8. 
   
9. void sol(){
   
10.   ll ans = 1, n = 0, m = 0, pos = 0;
    
11.   ll x;
    
12.   cin >> n >> x >> pos;
    
13.   ll xl = x - 1, xr = n - x;
    
14.   int l = 0, r = n;
    
15.   while(l < r){
    
16.     int mid = (l + r) >> 1;
    
17.     if(mid <= pos){
    
18.       l = mid + 1;
    
19.       if(mid < pos){
    
20.         ans = (ans * xl) % MOD;
    
21.         xl--;
    
22.       }
    
23.     }
    
24.     else{
    
25.       ans = (ans * xr) % MOD;
    
26.       xr--;
    
27.       r = mid;
    
28.     }
    
29.   }
    
30.   for(int i = 1; i <= xl + xr; ++i) ans = (ans * i) % MOD;
    
31.   cout << ans << '\n';
    
32. }
    
33. 
    
34. int main(){
    
35.   //io
    
36.   int t = 1;
    
37.   while(t--){
    
38.     sol();
    
39.   }
    
40. }
    
41. 
    

複製代碼