洛谷 4083 题解

题意简述

（题面很长，作者语死早，能这样不错了）
给定$n,d(n&lt;=1e5,d&lt;=1e9)$n,d(n<=1e5,d<=1e9)，以及$2n$2n个派。初始前$n$n在$Bessie$Bessie那里，后$n$n个在$Elsie$Elsie那里。每个派用两个值描述，$a$a和$b$b，表示$Bessie$Bessie的评分和$Elsie$Elsie的评分。然后$Bessie$Bessie和$Elsie$Elsie要互相送出去派，$Bessie$Bessie会先送一个手上有的派给$Elsie$Elsie，设$Bessie$Bessie给这个派的评分是$x$x，则$Elsie$Elsie会选一个她手上有的并且她评分在$[x,x+d]$[x,x+d]之间的派送给$Bessie$Bessie。然后设$Elsie$Elsie给送出去这个派的评分是$y$y，那么$Bessie$Bessie会送回来一个她手上有的并且评分在$[y,y+d]$[y,y+d]之间的派送回来给$Elsie$Elsie，以此类推。如果某人收到一个派，她认为这个派的评分是0，这个活动就结束了。输出$n$n行，第$i$i行表示如果$Bessie$Bessie送出了第$i$i个派，这样的活动几次能结束。无法结束输出$-1$−1。

数据

输入
2 1
1 1
5 0
4 2
1 4
输出
3
1

解释：

初始状态：

对于第一行，$Bessie$Bessie先送了评分是$(1,1)$(1,1)的派出去，如下图:

然后$Elsie$Elsie眼里这个派的评分是$1$1，它会送一个评分在$[1,2]$[1,2]之间的派给$Bessie$Bessie。这样的派只有一个，就是评分是$(4,2)$(4,2)的那个派。如下图：

然后$Bessie$Bessie眼里这个派的评分是$4$4，它会送一个评分在$[4,5]$[4,5]之间的派给$Elsie$Elsie。只有$(5,0)$(5,0)这个派满足条件。如下图：

此时$Elsie$Elsie收到了一个评分为$0$0的派，活动结束，所以第一行输出$3$3。

对于第二行，$Bessie$Bessie送了那个评分是$(5,0)$(5,0)的派，直接一次结束，因为此时$Elsie$Elsie收到了一个评分是$0$0的派。

思路

这个题目是我的一个考试题，并且没有中文翻译。在考试的时候，阅读也是花了我不少时间。当时我用了1:05AK了考试，别的题用了10分钟，这个题用了55分钟。不过这个题如果看懂了的话，并不是很难。

不难得到，我们珂以从反面考虑，即从目标节点（一个评分为$0$0的派）倒过来跑单源最短路，如果到不了设置为$-1$−1，然后$n$n个询问，每个都输出一下最短路即可。但是这个建图贼耗空间，并且写图多麻烦（链式前向星写法）。所以这个办法需要优化。
我们会发现，这个图上每个边的长度都是固定的为$1$1，所以我们不用建图，只要在遍历到$i$i的时候，有办法$\color{red}求$求出$i$i到哪些点，而$\color{red}不是存$不是存$i$i到哪些点，这样不就省很多空间了么？并且这样跑一遍广搜也是$O(n)$O(n)的。

珂是，怎么算点$i$i到哪些点呢。。。
维护两个$multiset$multiset，取名$sa,sb$sa,sb，分别表示$Bessie$Bessie和$Elsie$Elsie两人手里候选的派。$sa$sa按每个派的$b$b评分排序，$sb$sb按每个派的$a$a评分排序。每次考虑能送出去哪些派的时候，只要$lower_bound$lowerb​ound一下即可，如果满足条件，就删除掉候选，加入到队列，如果不满足条件了，因为$multiset$multiset是有序的，所以我们就再也找不到满足条件的了，直接$break$break掉。

代码:

#include<bits/stdc++.h>
#define N 200100
using namespace std;

int n,d;
int a[N],b[N],dis[N];
void Input()
{
    scanf("%d%d",&n,&d);
    for(int i=1;i<=(n<<1);i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        dis[i]=-1;//dis的初始值设置为-1
    }
}

struct cmp_a//sa的排序方法
{
    bool operator()(int x,int y) const
    {
        return b[x]>b[y];
    }
};
struct cmp_b//sb的排序方法
{
    bool operator()(int x,int y) const
    {
        return a[x]>a[y];
    }
};
multiset<int,cmp_a> sa;
multiset<int,cmp_b> sb;//sa和sb
int Q[N],head,tail;//队列
void Solve()
{
    for(int i=1;i<=n;i++)
    {
        if (b[i]==0)
        {
            Q[tail++]=i,dis[i]=1;
        }//珂以作为起点的先入队列
        else sa.insert(i);//否则入候选

        if (a[i+n]==0)
        {
            Q[tail++]=i+n,dis[i+n]=1;
        }
        else sb.insert(i+n);//差不多的道理
    }
    multiset<int,cmp_a> ::iterator isa;
    multiset<int,cmp_b> ::iterator isb;//sa和sb分开用，因为排序方式不同

    while(head<tail)
    {
        int i=Q[head++];//取队首
        if (i<=n)//在Bessie手里
        {
            while(1)
            {
                isb=sb.lower_bound(i);//lower_bound找一下
                if (isb==sb.end() or a[i]>a[*isb]+d)//不满足条件
                //找不到或者超过了范围
                {
                    break;//直接break，无FA♂珂说
                }
                dis[*isb]=dis[i]+1;
                Q[tail++]=*isb;
                sb.erase(isb);//否则就加入到队列，删除候选
            }
        }
        else//和上面差不多
        {
            while(1)
			{
				isa=sa.lower_bound(i);
				if(isa==sa.end() or b[i]>b[*isa]+d)
                {
                    break;
                }
				dis[*isa]=dis[i]+1;
				Q[tail++]=*isa;
				sa.erase(isa);
			}
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",dis[i]);
    }//输出每个dis即可
}

main()
{
    Input();
    Solve();
    return 0;
}