乒乓球

問題描述

Gob和Michael常在一起打乒乓球。他們是這樣決定比賽的輸赢的：比賽由若幹大局組成；誰最先赢下s大局誰就獲得比賽的勝利；在每一大局中，誰先得t分就獲得本大局的勝利。

在一次比賽中，他們隻記錄了比賽中的每一分是誰得的，但忘記了記錄s和t。現在給出比賽的每一分的得分情況，求出所有可能的s和t。Gob保證，得分表是完整的，也就是在比賽恰好在最後一人，得到最後一分後結束。

輸入格式(game.in)

第一行一個整數N，代表比賽一共得到了多少分。

第二行N個整數，代表比賽中每一分是誰得到的；1代表Gob，2代表Michael。

輸出格式(game.out)

第一行一個整數M，代表共有多少種可能的s,t情況。

接下來M行每行兩個整數si, ti，代表一種可能的s,t情況。M種情況按照s從小到大輸出；在s相等時按照t從小到大輸出。

樣例輸入1

5

1 2 1 2 1

樣例輸出1

2

1 3

3 1

樣例輸入2

5

1 2 2 2 1

樣例輸出2

樣例輸入3

10

1 1 2 1 1 1 2 2 1 1

樣例輸出3

3

1 7

3 2

7 1

資料範圍與限制

對于50%的資料，N<=1000；

對于100%的資料，1<=N<=100,000。

這是一道好題。

解法：

我們可以枚舉 t，對于某個t的值，那麼s的值也就确定了。

但是需要注意一些細節：

1.赢得比賽的人必須是赢得最後一局的人。

2.比賽必須進行到最後，即計分要記到n。

3.兩個人赢得局數不能相等。不能平局。

如果直接枚舉，時間複雜度大概是個O(n^2)。這樣可以得到70分。

N<=100000，可以聯想到時間複雜度應該是O(n*logn)，是二分吧！

我們可以用兩個數組分别記到某個位置Gob和Michael的得分字首和。

每一局，如果要赢的這一局，就要在上一局得分的基礎上在得t分，那就分别用二分在字首和上查找這個得分，那顯然是查找到的位置靠前的那個赢得這一局，那麼不斷更新得分，變換下标，一直到最後n。

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cmath>
#define MOD 1000000007
#define LL long long
using namespace std;
int n,maxn;
int G[100009],M[100009];
struct H{
    int s,t;
}ans[100009];int cnt; 
bool cmp(H x,H y)
{
    if(x.s<y.s) return 1;
    if(x.s==y.s&&x.t<=y.t) return 1;
    return 0;
} 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) 
    {
        int x;scanf("%d",&x);
        G[i]+=G[i-1];M[i]+=M[i-1];
        if(x==1) G[i]++;
        if(x==2) M[i]++;
    } 
    maxn=max(M[n],G[n]);
    for(int i=1;i<=maxn;i++)
    {
        int n1=0,n2=0,s1=0,s2=0,flag;
        int j=0;
        while(j<n)
        {
            int p1=s1+i;
            int p2=s2+i;
            int k1=lower_bound(G+j,G+n+1,p1)-G;
            int k2=lower_bound(M+j,M+n+1,p2)-M;
            j=min(k1,k2);
            if(k1<k2) {s1=p1,s2=M[j],n1++,flag=1;}
            else {s2=p2,s1=G[j],n2++,flag=2;} 
        } 
        if(j!=n||n1==n2) continue;
        if(n1<n2&&flag==1) continue;
        if(n2<n1&&flag==2) continue;
        ans[++cnt].s=max(n1,n2);
        ans[cnt].t=i;
    }
    sort(ans+1,ans+cnt+1,cmp);
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;i++)
    printf("%d %d\n",ans[i].s,ans[i].t);
    return 0;
}