ZeroJudge M851: Sleeping in hostels

同題:UVa 13181 – Sleeping in hostels

如同任何一位良好的背包客所知,沿著道路找到的青年旅舍通常擁有巨大的房間,床鋪一排又一排等待著被佔據。

儘管這些床鋪曾被無數人使用,疲憊讓每個人都不在乎躺在被歲月摧殘的床墊上,以便能夠一口氣睡上好幾個小時,為隔天養足精神。
事實上,為了最大化獲得良好的夜間睡眠,最重要的不是床墊的衛生狀況,而是離最近的背包客的距離。這是因為在你旁邊的床上有一位陌生人打呼聲,可能比一群蟎蟲更能毀了你的夜晚。
當你進入這樣的房間時,目標就是找到一張床,最大程度地與最近的背包客保持距離 (兩側都要考慮)。

範例測資

範例輸入範例輸出
輸入由多個測試案例組成,代表旅程中某一晚床鋪的佔用情況。
每一行代表一排床,包含一串由「.」和「X」構成的序列 (最多 500,000 個字元)。點 (「.」) 表示空床,而「X」表示有人佔用的床。保證至少有一張空床和一張被佔用的床
對於每個測試案例,請輸出一行,顯示您在所選床與最近鄰床之間可能擁有的最大空床數量
.X.X.
.X…X.
.X….X.
…X
0
1
1
2

解題思路

第一個和最後一個字元需要單獨判斷,其他的位置往左右兩邊找之後取最短的距離並且比較最大值並輸出即可。

範例程式碼-ZeroJudge M851: Sleeping in hostels

#include <iostream>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    string str;
    while (cin >> str)
    {
        int ans = -999;
        for (int i = 0; i<str.length(); i++)
        {
            if (str[i] == '.')
            {
                if (i == 0)
                {
                    int right = 0;
                    for (int j = i+1; j<str.length(); j++)
                    {
                        if (str[j] == 'X') break;
                        right++;
                    }
                    ans = max(ans, right);
                }
                else if (i == int(str.length())-1)
                {
                    int left = 0;
                    for (int j = i-1; j>=0; j--)
                    {
                        if (str[j] == 'X') break;
                        left++;
                    }
                    ans = max(ans, left);
                }
                else
                {
                    int right = 0;
                    for (int j = i+1; j<str.length(); j++)
                    {
                        if (str[j] == 'X') break;
                        right++;
                    }
                    int left = 0;
                    for (int j = i-1; j>=0; j--)
                    {
                        if (str[j] == 'X') break;
                        left++;
                    }
                    int check = min(right, left);
                    ans = max(check, ans);
                }
            }
        }
        cout << ans << "\n";
    }
}

//ZeroJudge M851
//Dr. SeanXD

發佈留言