算是一道考验思维的题吧,关键在于看出来如果要距离红球比篮球近的话那必然不能跨越篮球。那么就需要红球扎堆,也就是说红球扎堆的越多就有更多的胜利。
那么就到了统计红球的个数了。可以使用前缀和来求解。
#include <bits/stdc++.h> using namespace std; const int maxn = 5e5+10; //1代表红色,0代表蓝色 map<int, int, greater<int>> mp; map<int, int> ct; int main() { int T, n, m, cnt = 0, k; cin>>T; while (T--) { scanf("%d %d", &n, &m); ct.clear(); mp.clear(); cnt =0 ; int ans = 0; for (int i=0;i<n;i++) { scanf("%d", &k); ct[k]++; mp[k] = 1; } for (int i=0;i<m;i++) { scanf("%d", &k); mp[k]= 0; } //遍历一遍计算前缀和 for (auto p: mp) { if (p.second==1) cnt+=ct[p.first]; else cnt = 0; ans = max(ans, cnt); } if (ans==0) cout<<"Impossible\n"; else cout<<ans<<endl; } return 0; }