乒乓球

问题描述
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
0

样例输入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
",cnt);
    for(int i=1;i<=cnt;i++)
    printf("%d %d
",ans[i].s,ans[i].t);
    return 0;
}
原文地址:https://www.cnblogs.com/dfsac/p/7587881.html