Hướng dẫn giải của Bedao Mini Contest 15 - ROBOT


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

Để Robot có thể quay về vị trí ban đầu thì số lên di chuyển lên trên phải bằng số lần di chuyển xuống dưới và số lần di chuyển qua trái phải bằng số lần di chuyển qua phải. Nói cách khác, trong ~n~ kí tự, số kí tự ~U~ bằng số kí tự ~D~ và số kí tự ~L~ bằng số kí tự ~R~. Do đó ~n~ phải là số chẵn, nếu không sẽ không thể thay đổi sao cho thỏa mãn điều kiện trên được.

Gọi ~a~, ~b~ và ~x~, ~y~ lần lượt là số kí tự ~U~, ~D~ và ~L~, ~R~. Ta cần thay đổi ít nhất sao cho ~a = b~ và ~x = y~

Đáp án tối ưu sẽ là ~\frac{|a - b| + |x - y|}{2}~

Code mẫu

//TrungNotChung
#include <bits/stdc++.h>
#define pii pair<int , int>
#define fi first
#define se second
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x)  (1LL<<(x))
#define CNT(x) __builtin_popcountll(x)
#define task "tnc"  

using namespace std;
const int N = (int)3e5+282;
const int mod = (int)1e9+7;

int cnt[4];

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    for(int i=0; i<n; ++i)
    {
        if(s[i] == 'U') ++cnt[0];
        else if(s[i] == 'D') ++cnt[1];
        else if(s[i] == 'L') ++cnt[2];
        else if(s[i] == 'R') ++cnt[3];
    }

    if(n&1)
    {
        cout << -1;
        return;
    }

    int res = 1e9;
    for(int i=0; i<=n/2; ++i)
    {
        int x = i, y = (n - i*2) / 2;
        int tmp = abs(x - cnt[0]) + abs(x - cnt[1]) + abs(y - cnt[2]) + abs(y - cnt[3]);
        res = min(res, tmp/2);
    }
    cout << res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
    #endif // ONLINE_JUDGE
    solve();
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.