题目(翻译来自洛谷)

红队和蓝队在冰面上向目标区域滑动冰壶，距离目标区域中心最近的队伍获胜。

两支队伍在一条直线上竞争。比赛结束后，有 (n+m) 个冰壶在直线上, n 个是红队的，剩下 m 个是蓝队的。 红队的第 i 个冰壶被放在 a_i ，蓝队的第 i 个冰壶被放在 b_i 。

设 c 是中心。如果存在一些 i 使得 1 <= i <= n 并且对于所有 1 <= j <= m 都有 |c - a_i| < |c - b_j| 红队就赢得比赛。另外，如果满足条件的 i 的数目是 p ，则认为红队赢得 p 分。

给你红蓝两队的冰壶的位置，请你确定中心 c 的值，使红队得分最多。注意， c 是任意实数，不一定是整数。

输入

有很多测试样例。第一行输入一个整数 T ，表示样例数量。对于每个测试样列：

第一行包括两个整数 n 和 m (1 <= n, m <= 10^5) 分别表示红队和蓝队的冰壶数量。

第二行包括 n 个整数 a_1, a_2, ......, a_n (1 <= a_i <= 10^9) 表示红队的冰壶的位置。

第三行包括 m 个整数 b_1, b_2, ......, b_m (1 <= b_i <= 10^9)表示蓝队的冰壶的位置。

数据保证 n 的总和以及 m 的总和都不会超过 5 * 10^5 。

输出

每一个测试样列输出一行。如果存在 c 使得红队获胜且得分最多, 输出一个整数表示红队最大得分(不是 c).否则输出 Impossible ( 不带引号 ) 。

样例

样例输入 1

3
2 2
2 3
1 4
6 5
2 5 3 7 1 7
3 4 3 1 10
1 1
7
7

样例输出 1

2
3
Impossible

说明/提示

对于第一个样例，当 c = 2.5 时，红队的位于 2 和 3 的冰壶可以得分。

对于第二个样例，当 c = 7 时，红队的位于 5 和 7 的冰壶可以得分。

首先:要知道题目要求的是严格小于,所以如果一个位置既有红球,也有蓝球,那么没用.

PS:关于用map实现的方法,经过我一顿思考,发现尽然可以去掉一个map,直接使得代码运行时间短了近半

大概思路:我们以定下来的c点为中心,向左右扩散,直到到达第一个蓝球出现的地方停下来,中间的这一段的连续红球数(一个位置可以有多个红球)即是每次的答案.找到答案的最大值即是最终的答案

这一段思路也可以转化为:在两个蓝球的坐标之间(不包括边界),找连续红球个数.

AC代码1(直接用贪心+二分查找):

#include<iostream>
#include<algorithm>
#define maxn 500000+10
using namespace std;
int red[maxn],blue[maxn];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int t,n,m;cin>>t;
    while(t--)
    {
        cin>>n>>m;
      //不像map,这个是顺序存储的,可以不清空
        for(int i=1;i<=n;++i) {cin>>red[i];}
        for(int i=1;i<=m;++i) {cin>>blue[i];}
        sort(red+1,red+1+n);
        sort(blue+1,blue+1+m);
      //因为最左边,和最右边连续的红球也算(左(右)边没有蓝球了),所以我们假设两个虚拟的蓝球(一个在最左边取不到的位置,一个在最右边取不到的位置,比坐标的取值范围还大即可).在这之间的答案也有效
        blue[0]=0;blue[m+1]=1000000001;
        int ans=0;//把这个改成long,然后使用牛客中的clang++18,可以去掉后面的int类型强制转换
        for(int i=0;i<=m;++i)
        {
            ans=max(ans,
                    (int)//迭代器相减返回类型是有符号整型,但其类型不同平台有差异
                    (lower_bound(red+1,red+1+n,blue[i+1])//第一个>=的-1得到最后一个<的
                    -upper_bound(red+1,red+1+n,blue[i]))//第一个>的
                    //第一个>和最后一个<之间的红球数为答案.根据植树原理,还要+1,所以跟上面的-1抵消了
                   );
        }
        if(ans!=0) {cout<<ans<<'\n';}
        else {cout<<"Impossible\n";}//无有效红球,只有红蓝重合
    }
    return 0;
}

AC代码2(用map记录)

#include<iostream>
#include<map>
using namespace std;
map<int,int> count;//pos,count
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int t,n,m,tmp;cin>>t;
    while(t--){
       count.clear();//一定别忘了清零!!!
        cin>>n>>m;
        for(int i=1;i<=n;++i){
            cin>>tmp;
            ++count[tmp];//记录某个位置有几个红球
        }
        for(int i=1;i<=m;++i){
            cin>>tmp;
            count[tmp]=0;//题目要求的是严格小于,所以如果一个位置既有红球,也有蓝球,那么红球作废
          //坐标不在map里的就代表没球
        }
        int tmp=0,ans=0;
        for(auto it=count.begin();it!=count.end();++it){
            if(it->second==0) {tmp=0;}//遇到了蓝球,前面累计的红球作废
            else {tmp+=it->second;}//积累这个位置的红球
            ans=max(ans,tmp);//找到最大的连续红球串
        }
        if(ans!=0) {cout<<ans<<'\n';}
        else {cout<<"Impossible"<<'\n';}//无有效红球,只有红蓝重合
    }
    return 0;
}

PS: it-> , 相当于 (*it).