【Codeforces 1117C】Magic Ship

题意

【题解】

我们可以把这个行船的过程分解成两个过程
1.船经过时间t被风吹到了某个地方
2.船用这t时间尝试到达终点(x2,y2)

会发现如果时间t能最终能到达(x2,y2)的话

对于任意的时间t1>t,t1也能到达。

因为对于t后面的时间,比如t+1,那么风最多把船往偏离终点x,y的方向吹了一下,这一下总是能让多出来的时间(1单位时间)补回来的。

那么t-(船被吹了之后的位置与(x2,y2)的曼哈顿距离)肯定会随着t的增大而不下降。所以总是能到达的

所以它总是有一个下界的时间t1的。

我们只要二分这个时间t1就好

按照上面的思路,二分,然后判断船被吹了以后,能否到达(x2,y2),如果不能到就增加时间

【代码】

#include <bits/stdc++.h>

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i>= b;i--)

#define ll long long

using namespace std;

const int N = 1e5;

ll x1,y1,x2,y2,n;

ll pre[N+10][2];

string s;

ll get_mhd(ll x1,ll y1,ll x2,ll y2){

    return abs(x1-x2)+abs(y1-y2);

}

bool ok(ll t){

    ll xx = t/n*pre[n][0] + pre[(long long)t%n][0];

    ll yy = t/n*pre[n][1] + pre[(long long)t%n][1];

    ll tx = x1 + xx,ty = y1 + yy;

    ll temp = get_mhd(tx,ty,x2,y2);

    if (temp<=t) return true;

    return false;

}

int main(){

    ios::sync_with_stdio(0),cin.tie(0);

    cin >> x1 >> y1 >> x2 >> y2;

    cin >> n;

    cin >> s;

    rep1(i,0,(int)s.size()-1){

        rep1(j,0,1) pre[i+1][j] = pre[i][j];

        if (s[i]=='U'){

            pre[i+1][1]++;

        }

        if (s[i]=='D'){

            pre[i+1][1]--;

        }

        if (s[i]=='L'){

            pre[i+1][0]--;

        }

        if (s[i]=='R'){

            pre[i+1][0]++;

        }

    }

    ll l = 1,r = 2e14,temp = -1;

    while (l<=r){

        ll mid = (l+r)>>1;

        if (ok(mid)){

            temp = mid;

            r = mid - 1;

        }else l = mid + 1;

    }

    cout<<temp<<endl;

    return 0;

}

巴特西

【Codeforces 1117C】Magic Ship

最新文章

热门文章