首页 > 代码库 > Codeforces 496D Tennis Game 枚举+二分

Codeforces 496D Tennis Game 枚举+二分

2024-08-09 05:49:30   217人阅读

给定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);


[cpp] view plaincopy
    1. import java.util.ArrayList;  
    2. import java.util.Collections;  
    3. import java.util.List;  
    4. import java.util.Scanner;  
    5. public class Main {  
    6.     class Ans implements Comparable<Ans>{  
    7.         int s, t;  
    8.         public Ans(int a, int b){  
    9.             s = a; t = b;  
    10.         }  
    11.         public int compareTo(Ans o){  
    12.             if(s != o.s)return Integer.compare(s, o.s);  
    13.             return Integer.compare(t, o.t);  
    14.         }  
    15.     }  
    16.     static int N = 100050;  
    17.     int[] a = new int[N], b = new int[N], w = new int[N];  
    18.     int at, bt, n;  
    19.     ArrayList<Ans> ans = new ArrayList<>();  
    20.     void init(){  
    21.         n = cin.nextInt();  
    22.         for(int i = 1; i <= n; i++)  
    23.             w[i] = cin.nextInt();  
    24.         at = bt = 0;  
    25.         a[at++] = 0; b[bt++] = 0;  
    26.         for(int i = 1; i <= n; i++)  
    27.         {  
    28.             if(w[i]==1)  
    29.                 a[at++] = i;  
    30.             else   
    31.                 b[bt++] = i;  
    32.         }  
    33.         at--; bt--;  
    34.         ans.clear();  
    35.     }  
    36.     void add(int x, int y){  
    37.         Ans tmp = new Ans(x, y);  
    38.         ans.add(tmp);  
    39.     }  
    40.     void work(int x){  
    41.         int na = 0, nb = 0;  
    42.         int siza = 0, sizb = 0;  
    43.     //  System.out.println(x+":"+at+" "+bt);  
    44.         while(true){  
    45.             if(na == at && nb == bt)break;  
    46.             if(na+x > at && nb+x > bt)return ;  
    47.         /*  if(na+x > at) 
    48.             { 
    49.                 if(nb+x == bt){ 
    50.                 sizb++; break ; 
    51.                 } 
    52.                 return ; 
    53.             } 
    54.             if(nb+x > bt) 
    55.             { 
    56.                 if(na+x == at){ 
    57.                 siza++; break ; 
    58.                 } 
    59.                 return ; 
    60.             }/**/  
    61.             if( na+x<=at &&(nb+x>bt || a[na+x] < b[nb+x]))  
    62.             {  
    63.                 siza++;  
    64.                 na += x;  
    65.                 int L = 0, R = bt, pos = 0;  
    66.                 while(L <= R)  
    67.                 {  
    68.                     int mid = (L+R)>>1;  
    69.                     if(b[mid] < a[na])  
    70.                     {  
    71.                         pos = mid;  
    72.                         L = mid+1;  
    73.                     }  
    74.                     else   
    75.                         R = mid-1;  
    76.                 }  
    77.                 nb = pos;  
    78.             }  
    79.             else if(nb+x <= bt)  
    80.             {  
    81.                 sizb++;  
    82.                 nb += x;  
    83.                 int L = 0, R = at, pos = 0;  
    84.                 while(L <= R)  
    85.                 {  
    86.                     int mid = (L+R)>>1;  
    87.                     if(a[mid] < b[nb])  
    88.                     {  
    89.                         pos = mid;  
    90.                         L = mid+1;  
    91.                     }  
    92.                     else   
    93.                         R = mid-1;  
    94.                 }  
    95.                 na = pos;  
    96.             }  
    97.             else return;  
    98.     //      System.out.println("["+na+" "+nb+"]"+"{"+siza+" "+sizb+"}");  
    99.         }/**/  
    100.     //  System.out.println("last:"+siza+" "+sizb);  
    101.         if(siza == sizb)return;  
    102.         if(siza>sizb && w[n] == 1)  
    103.             add(siza, x);  
    104.         else if(siza<sizb && w[n] == 2)  
    105.             add(sizb, x);  
    106.     }  
    107.     public void work(){  
    108.         init();  
    109.     //  int aaa = 0; if(aaa<=0){System.out.println("debug"); return ;}  
    110.         for(int i = 1; i <= n; i++)  
    111.             work(i);  
    112.         System.out.println(ans.size());  
    113.         Collections.sort(ans);  
    114.         for(int i = 0; i < ans.size(); i++)  
    115.             System.out.println(ans.get(i).s+" "+ans.get(i).t);  
    116.     }  
    117.     Main() {    
    118.         cin = new Scanner(System.in);    
    119.     }    
    120.     public static void main(String[] args) {  
    121.         Main e = new Main();    
    122.         e.work();  
    123.     }  
    124.     public Scanner cin;  
    125. } 

Codeforces 496D Tennis Game 枚举+二分


联系
我们