题解：P14330 [JOI2021 预选赛 R2] 往返滑道 / Round Sugoroku

· · 题解

吐槽：我的复杂度似乎不太对，限制是 1s 就超时了

P14330 [JOI2021 预选赛 R2] 往返滑道 / Round Sugoroku

分析

直接暴力的话，恭喜你，40 分。
那我们就用 vector 记录一下每个 # 的位置，每次二分查找棋子下一个 # 的位置（将 x 看作 #），ans 加上这个位置减去棋子位置的绝对值。如果这个位置是 x，那棋子还得往前走一步，ans 加 1。不是的话就删去这个这个位置。最后没有 # 的时候，就输出 ans。

上代码！！！

#include<bits/stdc++.h>
using namespace std;
int n,a,b=1,ans,sum;
char s[200001];
vector<int>e;
int main() {
//  freopen("a.in","r",stdin);
    scanf(" %d %d\n%s",&n,&a,s+1);
    e.push_back(0);//记录第一个x
    for(int i=1; i<=n; i++)if(s[i]=='#')e.push_back(i);
    e.push_back(n+1);//这一步必须在把#的位置记录完过后，再记录第二个x，不然还得排序
    while(1) {
        vector<int>::iterator x;
        if(b)x=lower_bound(e.begin(),e.end(),a);
        else x=upper_bound(e.begin(),e.end(),a)-1;
        ans+=abs((*x)-a);//记得abs
        b=!b;
        a=*x;
        if(a==n+1) {
            a--;
            ans++;//ans记得加1
        } else if(a==0) {
            a++;
            ans++;//同上
        }
        if((*x!=0)&&(*x!=n+1))/*是#就删除*/e.erase(x);
        if(e.size()==2)/*判断是否等于2，是因为还剩下两个x*/return printf("%d",ans),0;
    }
    return 0;
}

求赞qwp