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;
}