题解 P6283 【[USACO20OPEN] The Moo Particle S】

· · 题解

写在前面的话

苏格拉底曾指出，求得知识的最好办法是有系统的问与答，故本题解采用了该种方式。

思路分享

问：这道题你怎么看？

答：首先看到这道题时，我们可能会想到二位偏序，但是很遗憾地告诉大家，这道题用二位偏序并不能解决。

问：为什么不能解决呢？

答：考虑对于 1 个点，若此时将这个点加入了树状数组中，那么如何计算它的贡献呢？我们并不能在给定的时间中将这个贡献计算出来。

问：那么我们该怎么做呢？

答：考虑转化为一道图论题，若粒子 x 与粒子 y 之间可以发生作用，就在粒子 x 与粒子 y 之间连一条无向边。

问：为什么要这么做呢？

答：因为我们可以发现，若一些粒子处于一个连通块中，那么这些粒子就可以经过一番相互作用之后变为 1 个粒子，而若两个粒子不在一个连通块中，那么这两个连通块再怎么相互作用也只可能变成 2 个粒子。

问：但是这样仍是 \Theta(n^2) 的，怎么优化呢？

答：考虑使用二位偏序的思想，将这些点以 y 为关键字排序，我们就可以仅考虑 x 一维了。

问：那么如何计算答案呢？

答：考虑使用并查集的思想，若排序后，一个粒子可以与它前面的粒子相互作用，那么就将这两个点连接起来，否则就计算一次贡献。

问：乍一看感觉很对呢，这就是正解了吧？

答：先别着急，我们先来看看这个思路的代码实现。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100100;
int n,Min;
struct node{
    int x,y;
    bool operator<(node u)const{
        return y==u.y?x>u.x:y<u.y;
    }//x坐标需要从大到小排序
    //因为如果两个粒子y坐标相同，那么x较大的更有可能与其他粒子互相作用，从而获得更小答案。
}moo[maxn];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&moo[i].x,&moo[i].y);
    }
    stable_sort(moo+1,moo+1+n);
    Min=1000000001;
    moo[0].y=-1000000001;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(moo[i].x<Min&&moo[i].y!=moo[i-1].y){
            ans++;//若与前面的粒子无法发生互相作用，那么将答案加1
        }
        Min=min(Min,moo[i].x);
    }
    printf("%d",ans);
    return 0;
}

答：看完之后，可以发现其实这个方法是错误的，只能通过前两个测试点（也就是两个样例）

问：为什么它是错的呢？乍一看感觉很对呢。

答：我们可以考虑如下图中的三个粒子。

答：按照这种方式排好序之后，我们就可以得到三个粒子 1、2、3。通过这份代码所计算出来的答案是 2 ，两次贡献分别在点 1 与 2 处产生，但是其实正确的答案为 1，即 3 粒子与另外两个粒子互相作用并使这两个粒子消失。

问：那好吧。那么我们还可以怎样做呢？

答：我们不妨设 l_i 为粒子 1 \sim i 的 x 坐标的最小值，r_i为粒子 i \sim n 的 x 坐标的最大值，那么我们可以发现，若对于某个粒子 i，若 l_i > r_i+1，即粒子 i 前面的所有粒子的 x 坐标最小值还要大于后面所有粒子的 x 坐标最大值，那么又因为我们已经将所有粒子按照 y 坐标从小到大排序了，那么对于所有 i \in \left[ 1,i \right],j \in \left( i,n \right]，都有 x_i > x_j 且 y_i \leqslant y_j，即 \left[ 1,i \right] 与 \left( i,n \right] 不可能在一个连通块中，就可以将答案加 1。

问：那么这就是正解了吗？

答：是的。

正解代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=100100;
int n;
int l[maxn],r[maxn];
struct node{
    int x,y;
    bool operator<(node u)const{
        return y==u.y?x<u.x:y<u.y;
    }//与前面差不多的排序，但是y坐标相同时x坐标需改成从小到大
}moo[maxn];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&moo[i].x,&moo[i].y);
    }
    stable_sort(moo+1,moo+1+n);
    l[1]=moo[1].x;
    for(int i=2;i<=n;i++){
        l[i]=min(l[i-1],moo[i].x);
    }//处理l
    r[n]=moo[n].x;
    for(int i=n-1;i>=1;i--){
        r[i]=max(r[i+1],moo[i].x);
    }//处理r
    int ans=1;//这里ans的初始值需要赋为1
    for(int i=1;i<n;i++){
        if(l[i]>r[i+1]){
            ans++;
        }
    }
    printf("%d",ans);
    return 0;
}