Code Jam 2017 Qualification Round Problem C. Bathroom Stalls

admin管理员组

文章数量:1558103

Problem C. Bathroom Stalls

题意

A certain bathroom has N + 2 stalls in a single row; the stalls on the left and right ends are permanently occupied by the bathroom guards. The other N stalls are for users.

Whenever someone enters the bathroom, they try to choose a stall that is as far from other people as possible. To avoid confusion, they follow deterministic rules: For each empty stall S, they compute two values LS and RS, each of which is the number of empty stalls between S and the closest occupied stall to the left or right, respectively. Then they consider the set of stalls with the farthest closest neighbor, that is, those S for which min(LS, RS) is maximal. If there is only one such stall, they choose it; otherwise, they choose the one among those where max(LS, RS) is maximal. If there are still multiple tied stalls, they choose the leftmost stall among those.

K people are about to enter the bathroom; each one will choose their stall before the next arrives. Nobody will ever leave.

When the last person chooses their stall S, what will the values of max(LS, RS) and min(LS, RS) be?

解法

数据结构

本题 K 个人选择位置的策略是一个固定方案。可以等价的看作是下述选择策略：

1. 对于第 i 个人选择座位，选择的必然是连续最长的无人座位区间 [l, r] 。
2. 若存在多个连续最长的无人座位区间 [l, r] ，选择 l 最小的区间。（当然，这个选择不对最后结果产生影响想错了也无所谓）。
3. 定义该区间 [l, r] 的长度为 N
   
   • 若 N 为偶数，则选择的座位为 ⌊l+r2⌋ $\lfloor \frac{l+r}{2}\rfloor$ ，该区间被划分成新的 [l, (l+r)/2 - 1] 和 [(l+r)/2+1, r] 。
   • 若 N 为奇数，则选择的座位为 l+r2 $\frac{l+r}{2}$ ，该区间被划分成新的 [l, (l+r)/2 - 1] 和 [(l+r)/2+1, r] 。

所以当存在若干等长最长区间 [l, r] 时，都将被直接划分成 [l, (l+r)/2 - 1] 和 [(l+r)/2+1, r] 。

问题只考虑求第 K 个人选择的位置的 LS 与 RS，故不需要具体考虑该位置的坐标，只需要知道该人选择的位置的区间长度即可。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<fstream>
#include<queue>
#include<map>
using namespace std;
long long n, k, idx, ansMin, ansMax;
map<long long, long long> mp;
void solve()
{
    long long p, q, t, cnt;
    idx = 0;
    mp.clear();
    priority_queue<long long> que;
    que.push(n);
    mp[n] = 1;
    while(!que.empty())
    {
        p = que.top();
        que.pop();
        cnt = mp[p];
        idx += cnt;
        if(p % 2 == 0)
        {
            t = p/2 - 1;
            q = p/2;
        }
        else
        {
            t = p/2;
            q = p/2;
        }
        if(mp[q])
            mp[q]+=cnt;
        else
        {
            mp[q] = cnt;
            que.push(q);
        }
        if(mp[t])
            mp[t]+=cnt;
        else
        {
            mp[t] = cnt;
            que.push(t);
        }
        if(idx >= k)
        {
            ansMin = t;
            ansMax = q;
            return;
        }
    }
}
int main()
{
    freopen("G:\\C.in", "r", stdin);
    freopen("G:\\C.out", "w", stdout);
    int T;
    scanf("%d",&T);
    for(int ica=1;ica<=T;ica++)
    {
        scanf("%I64d %I64d", &n, &k);
        solve();
        printf("Case #%d: %I64d %I64d\n", ica, ansMax, ansMin);
    }
}

本文标签： JamCodequalificationStallsBathroom