[ICPC2020南京L] Let‘s Play Curling - 双指针
Description
给定长度为n的整数数组a，和长度为m的整数数组b，表示在一维数轴上有n个红点 \(a[i]\),和m个蓝点 \(b[i]\)，给定一个实数c，对于每一个i，如果对于所有的j，都满足 \(|c-a[i]|<|c-b[j]|\)，那么红队分数+1，现在你可以自定义c的值，计算红队可能获得的最大分数.
Solution
其实就是计算两个蓝点严格夹的区间中最多有多少个红点，双指针即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int n, m, a[N], b[N];
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++)
cin >> b[i];
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
a[0] = b[0] = -9e9;
a[n + 1] = b[m + 1] = 9e9;
int ans = 0;
int pos = 1;
for (int i = 1; i <= m + 1; i++)
{
// 可用区间 (b[i-1], b[i])
int cnt = 0;
while (a[pos] < b[i] && pos <= n)
{
cnt += a[pos] > b[i - 1];
++pos;
}
ans = max(ans, cnt);
}
if (ans)
cout << ans << endl;
else
cout << "Impossible" << endl;
}
signed main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--)
solve();
}