maiktom 2020-01-14
题目链接:http://codeforces.com/problemset/problem/600/B
题目大意:
给你一个长度为 \(n\) 的数组 \(a[]\) 和一个长度为 \(m\) 的数组 \(b[]\) 。
对于数组 \(b[]\) 中的每一个元素 \(b_j\) ,你需要计算出 \(a[]\) 中有多少元素 \(a_i\) 是满足 \(a_i \le b_j\) 的。
解题思路:
本题涉及算法:二分。
需要先将数组 \(a[]\) 排序,然后对于每一个 \(b_j\) ,二分查找大于等于 \(b_j\) 的最小的那个数。
实现代码如下:
#include <bits/stdc++.h> using namespace std; const int maxn = 200020; int n, m, a[maxn], b[maxn]; 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]; sort(a, a+n); for (int i = 0; i < m; i ++) { if (i) putchar(' '); int L = 0, R = n-1, res = -1; while (L <= R) { int mid = (L + R) / 2; if (a[mid] <= b[i]) { res = mid; L = mid + 1; } else { R = mid - 1; } } cout << res + 1; } cout << endl; return 0; }
当然,我们也可以使用 STL 的 upper_bound 函数来实现(upper_bound 函数返回大于某一个元素的最小的那个数的地址),实现的代码如下:
#include <bits/stdc++.h> using namespace std; const int maxn = 200020; int n, m, a[maxn], b[maxn]; 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]; sort(a, a+n); for (int i = 0; i < m; i ++) { if (i) putchar(' '); int id = upper_bound(a, a+n, b[i]) - a; cout << id; } cout << endl; return 0; }