把每个佣兵团勇士的攻击力排序，再把所有勇士的攻击力合起来排序，枚举第i个佣兵团的第j个勇士，其攻击力为，要想找到一个满足条件的勇士，其攻击力需大于，先从所有勇士中二分搜索得到第一个攻击力大于的勇士，那么这个勇士和后面的勇士都满足条件，但是要去掉同一个佣兵团的勇士，再在中二分搜索找到第一个攻击力大于的勇士，减掉即可
本题考察 二分，STL的运用，时间复杂度
#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
#include <cstdio>
#define int long long
using namespace std;
int t, n, k;
int sv[100010], v[1010][110], a[1010];
signed main() {
cin >> t;
while (t--) {
int ans = 0, len = 0;
scanf("%lld%lld", &n, &k);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
for (int j = 1; j <= a[i]; ++j) {
scanf("%lld", &v[i][j]);
sv[++len] = v[i][j];
}
sort(v[i] + 1, v[i] + 1 + a[i]);
}
sort(sv + 1, sv + 1 + len);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= a[i]; ++j) {
ans += len - (lower_bound(sv + 1, sv + 1 + len, k - v[i][j]) - sv) + 1;
ans -= a[i] - (lower_bound(v[i] + 1, v[i] + 1 + a[i], k - v[i][j]) - v[i]) + 1;
}
}
cout << ans / 2 << endl;
}
return 0;
}
共 2 条回复
@071maozihan 看到了看到了，用毛线段树啊，lower_bound 不香么
cookiebus,老毛用的线段树