B. Number of Smaller

題目內容

給予兩個陣列，均為已排序遞增陣列，個別長度為 $n$ 和 $m$ ，對於第二個陣列的每個元素，找到第一個陣列中，比目前元素小的元素數。

輸入 : 第一行有兩整數 $n$ 和 $m$ $(1 \le n, m \le 10^5 )$ ， 代表兩陣列長度。第二行有 $n$ 個整數 $a_i$ ，代表第一個陣列的元素，第三行有 $m$ 個整數 $b_i$ ，代表第一個陣列的元素 $(−10^9 \le a_i, b_i \le 10^9)$

輸出 : 輸出 $m$ 個數字，代表 $b_i$ 與第一個陣列中，比 $b_i$ 小的元素數。

解題想法

本題目是章節中所提到的進階題，尚不了解者可以返回閱讀

在此宣告兩陣列 $a$, $b$ ，個別長度為 $n$ 和 $m$ ，並且宣告一變數 $now$ ，用於紀錄與第一個陣列中，比目前元素小的元素數。

因此，在走訪 $b$ 陣列所有元素時，可以利用一 while 迴圈來檢測 $a_{now}$ 是否較目前元素小，否則中止此迴圈。

在每次迴圈的最後，都要輸出 now , 代表第一個陣列中，比 $b_{now}$ 小的元素數，並且輸出保持嚴格比對。

範例程式

#include <bits/stdc++.h>
#define LL long long
using namespace std;

LL n, m, a[200005], b[200005], now = 0;

int main() {
	cin >> n >> m;	
	for (int i = 0; i < n; i++) cin >> a[i]; 
	for (int i = 0; i < m; i++) cin >> b[i];
	a[n] = INT_MAX;	
	for (int i = 0; i < m; i++) {
		while (a[now] < b[i]) now++;
		if (i) cout << ' ';
		cout << now;
	}
	cout << '\n';
	return 0;
}