自动搬运

查看原文

来自洛谷，原作者为

	fish_love_cat 「要毁灭世界，根本不需要邪恶。起初，那些都是不会被任何人怪罪的小小愿望。而那样的愿望却如此轻易地，和末日相连在一起。」

搬运于2025-08-24 23:13:09，当前版本为作者最后更新于2025-04-12 19:02:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

赛时想抢首杀，第一个开的就是这题。

然后爆炸了，先去写了其他题转回来才发现自己糖成啥了。

最左端显然必须消耗操作，然后就是从下往上遍历会劣于从上往下遍历。

因为当前列最下面的点能消的较低点上面一定消不掉，但如果从它开始，它会锁定到上面可能能消的点，那这样上面的贡献就被挤掉了。

于是你像我一样对每一列写了个可删堆模拟每次操作发现挂了。

考虑这么一张图：

...@
.@@.
.@..
@.@.

@ 表示棋子，. 表示空地。

我们的做法：

...1
.21.
.1..
1.3.

答案为 $3$。

正解：

...1
.11.
.2..
2.2.

答案为 $2$。

这启示我们对于每一个棋子进行转移而不是直接模拟。

从左到右从上到下的枚举棋子，然后从能抵达它并且未使用的棋子中取最上面的点进行转移。

无法转移的计入答案。

然后你会发现做完了，时间复杂度综合 $O(n \log n)$，瓶颈在于排序。

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int>ve[1000005];
map<int,bool>mp[1000005];
bool cmp(int a,int b){
    return a>b;
}
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int u,v;
        cin>>u>>v;
        mp[u][v]=1;
        ve[u].push_back(v);
    }
    int ans=0;
    for(int i=1;i<=1000000;i++){
        if(ve[i].size()==0)continue;
        sort(ve[i].begin(),ve[i].end(),cmp);
        for(int j=0;j<ve[i].size();j++){
            if(mp[i-1][ve[i][j]+1])mp[i-1][ve[i][j]+1]=0;
            else if(mp[i-1][ve[i][j]])mp[i-1][ve[i][j]]=0;
            else if(mp[i-1][ve[i][j]-1])mp[i-1][ve[i][j]-1]=0;
            else ans++;
        }
    }
    cout<<ans;
    return 0;
}