题目链接：点击打开链接
题意：
给定n场比赛。
下面n个数字：表示该场是1获胜还是2获胜。
1、胜利者获得一分。
2、若已经决出整个赛季的胜负则比赛不会继续。
3、设要赢得这个赛季需要赢有s局，每局先获得t分的选手胜利。
问：
找出所有的(s,t)组合使得给定的n场比赛记录合法。
输出要排序。
枚举t。
a数组存第一个人赢的哪些场次。
b数组存第二个人赢的哪些场次。
设赢t分为一句。则判断 第一个人再赢t分是第几场，第二个人再赢t分是第几场。
显然先赢得t分的人赢了这场。
这样同时跑2个人的场数。
复杂度：
设要赢的分数为i， 则这个数组最多枚举 n/i次
i = [1, n]
所以复杂度 = n/1 + n/2 + ??? + n/n = nln(n+1);
其中有个二分。总复杂度是 O( n * ln(n+1) * log n);
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Main {
class Ans implements Comparable
{
int s, t;
public Ans(int a, int b){
s = a; t = b;
}
public int compareTo(Ans o){
if(s != o.s)return Integer.compare(s, o.s);
return Integer.compare(t, o.t);
}
}
static int N = 100050;
int[] a = new int[N], b = new int[N], w = new int[N];
int at, bt, n;
ArrayList
ans = new ArrayList<>(); void init(){ n = cin.nextInt(); for(int i = 1; i <= n; i++) w[i] = cin.nextInt(); at = bt = 0; a[at++] = 0; b[bt++] = 0; for(int i = 1; i <= n; i++) { if(w[i]==1) a[at++] = i; else b[bt++] = i; } at--; bt--; ans.clear(); } void add(int x, int y){ Ans tmp = new Ans(x, y); ans.add(tmp); } void work(int x){ int na = 0, nb = 0; int siza = 0, sizb = 0; // System.out.println(x+":"+at+" "+bt); while(true){ if(na == at && nb == bt)break; if(na+x > at && nb+x > bt)return ; /* if(na+x > at) { if(nb+x == bt){ sizb++; break ; } return ; } if(nb+x > bt) { if(na+x == at){ siza++; break ; } return ; }/**/ if( na+x<=at &&(nb+x>bt || a[na+x] < b[nb+x])) { siza++; na += x; int L = 0, R = bt, pos = 0; while(L <= R) { int mid = (L+R)>>1; if(b[mid] < a[na]) { pos = mid; L = mid+1; } else R = mid-1; } nb = pos; } else if(nb+x <= bt) { sizb++; nb += x; int L = 0, R = at, pos = 0; while(L <= R) { int mid = (L+R)>>1; if(a[mid] < b[nb]) { pos = mid; L = mid+1; } else R = mid-1; } na = pos; } else return; // System.out.println("["+na+" "+nb+"]"+"{"+siza+" "+sizb+"}"); }/**/ // System.out.println("last:"+siza+" "+sizb); if(siza == sizb)return; if(siza>sizb && w[n] == 1) add(siza, x); else if(siza