题解 | #Let's Play Curling#

• 题目考点：离散化（其实怎么写都行，以个人目前能力感觉离散化+前缀和比较好上手）
• 题目大意：一条线上红蓝两种石头随机排列，易知存在若干点使得这些点前后均为红色石头，且绝对不含蓝色石头，找到这些点中的前后红色石头数量最多的那个点，输出最大数量
• 题目分析：
  
  如图，我们可以确定a[4]和a[5]之间的点，前后含有红色石头最多（绝对不含有蓝色），因此我们的目标就是以相邻两个蓝色石头为基准，计算他们之间红色石头的数量（即连续红色石头区间）的最大值；计算区间和，首先想到前缀和（假定我们不知道线段树 =_=||）；
• 注意点：
  1、对于这道题，存在数组最前面和最后面是红色石头的情况，因此我们在a[ 0 ] 和a [ 1e9 + 1 ]处放置两个蓝色石头，这样就可以做到不遗漏了；
  2、如果一个地方既有红色又有蓝色石头，那么根据题意，该点的红色石头就不能算进答案去（如图中的 6 、 7 号）

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;
typedef pair<int, int> PII;

const int N = 100010, INF = 0x3f3f3f3f;
vector<PII> a;
map<int, int> mp;
int b[N];

int main()
{
    int t; scanf("%d", &t);
    while(t--)
    {
        a.clear();
        mp.clear();

        int n, m;
        scanf("%d%d", &n, &m);

        for(int i = 1; i <= n; i++)
        {
            int x;
            scanf("%d", &x);
            mp[x] ++ ;
        }

        for(int i = 1; i <= m; i++)
            scanf("%d", &b[i]);
        sort(b + 1, b + m + 1); //蓝色石头排序
        b[m + 1] = 1e9 + 1;  //0 和 1e9 + 1分别放一个蓝色石头计算边界

        int sum = 0;
        for(PII u : mp)
        {
            a.push_back({u.first, sum});
            sum += u.second;
        }
        a.push_back({INF, sum});

        int ans = 0;
        for(int i = 0; i <= m; i++)
        {                                    //这里+1和-1避免了图中6、7号的情况
            auto p1 = upper_bound(a.begin(), a.end(),(PII){b[i]+1,  -INF});
            auto p2 = upper_bound(a.begin(), a.end(),(PII){b[i+1]-1, INF});
            ans = max(ans, p2 -> second - p1 -> second);
            //cout<<b[i]+1<<' '<<b[i+1]-1<<' '<<p2 -> second - p1 -> second<<"**";
        }
        if(ans)printf("%d\n", ans);
        else puts("Impossible");    //I大写！  I大写！  I大写！！！！！呜呜呜呜呜呜
    }

    return 0;
}

因为i没大写wa了四发TAT