用b切割a时,对每一个ai都找bj作切割,找bj使用二分
代码:
#include <bits/stdc++.h> using namespace std; const long long int maxn = 500050; long long int a[maxn]; long long int n, x, m, sum; long long int b[maxn]; bool check(long long int k) { // ai是否在b中 long long int l = 1, r = m, mid; while (l <= r) { mid = (l + r) / 2; if (k < b[mid]) { r = mid-1; } else if (k > b[mid]) { l = mid + 1; } else return 1; } return 0; } int main() { cin >> n >> m; for (long long int i = 1; i <= n; i++) { scanf("%lld", &a[i]); } for (long long int i = 1; i <= m; i++) { scanf("%lld", &b[i]); } long long int ans = 0; sort(b + 1, b + m + 1); //二分b前要先对b排序 for (long long int i = 1; i <= n; i++) { if (check(a[i])) { // 能否被切割 a[i] = 0; } } long long int flag = 0; for (long long int i = 1; i <= n; i++) { if (a[i] != 0 && flag == 0) { flag = 1; ans++; } if (a[i] == 0 && flag == 1) { flag = 0; } } cout << ans; }