AtCoder Petrozavodsk Contest 001 C – Vacant Seat 交互题、带分类讨论的二分

C - Vacant Seat 交互题、带分类讨论的二分

My Solution

题意：交互题，有一个周长为n的环形（3<=n<=99999），每一格是一个座位，每个位置要么坐着一个男人M要么女人F要么空的V，但安排座位M和M不能并列且F和F不能并列，所以n个座位中至少一个座位是空着的，通过交换的方式在20步之内找出一个空着的座位的坐标。

交互题、带分类讨论的二分

先输出l = 0 和 r = n-1，分别记录 a[l] 和 a[r]的是M或者F或者V。

然后二分mid，

然后r和mid之间有(r - mid - 1)个位置，

如果有奇数个位置，则当a[r] == a[mid]时，则在(l,mid)中必定有V 故r = mid，否则(mid, r)中必定有V故 l = mid。

如果有偶数个位置，则当a[r] ！= a[mid]时，则在(l,mid)中必定有V 故r = mid，否则(mid, r)中必定有V故 l = mid。

时间复杂度 O(logn)

空间复杂度 O(n)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 8;
 
string s;
int a[MAXN];
int main()
{
    #ifdef LOCAL
    //freopen("c.txt", "r", stdin);
    //freopen("c.out", "w", stdout);
    int T = 1;
    while(T--){
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);
 
    LL n, i, l, r, mid;
    bool f;
    cin >> n;
    l = 0, r = n - 1;
 
    cout << l << "n"; fflush(stdout); cin >> s;
    if(s[0] == 'M'){
        a[l] = 1;
    }
    else if(s[0] == 'F'){
        a[l] = 2;
    }
    else{
        a[l] = -1;
        return 0;
    }
 
    cout << r << "n"; fflush(stdout); cin >> s;
    if(s[0] == 'M'){
        a[r] = 1;
    }
    else if(s[0] == 'F'){
        a[r] = 2;
    }
    else{
        a[r] = -1;
        return 0;
    }
 
    while(l + 1 < r){ mid = (l+r)>>1;
        cout << mid << "n"; fflush(stdout); cin >> s;
        if(s[0] == 'M'){
            a[mid] = 1;
        }
        else if(s[0] == 'F'){
            a[mid] = 2;
        }
        else{
            a[mid] = -1;
            return 0;
        }
 
        if((r - mid - 1)&1){
            if(a[mid] == a[r]){
                r = mid;
            }
            else{
                l = mid;
            }
        }
        else{
            if(a[r] != a[mid]){
                r = mid;
            }
            else{
                l = mid;
            }
        }
    }
 
 
    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

问题Source

AtCoder Petrozavodsk Contest 001

Thank you!

                                                                                                                                             ------from ProLightsfx