package xpc.sort;

 import java.util.Scanner;

 /**

  * 瑞士轮问题实现

  *

  * @author xpc

  *

  */

 public class RuiShiLun {

     public static void main(String[] args) {

         RuiShiLun obj = new RuiShiLun();

         int no[];//每个选手的编号，顺序按名次

         int s[];

         int w[];

         Scanner scanner = new Scanner(System.in);

         System.out.println("请输入N R Q");

         String  str = scanner.nextLine();

         String [] temp = str.split(" ");

         int n = Integer.parseInt(temp[0]);

         int r = Integer.parseInt(temp[1]);

         int q = Integer.parseInt(temp[2]);

         no = new int[2*n];

         s = new int[2*n];

         w = new int[2*n];

         System.out.println("请输入对应编号选手初始分数：");

         str = scanner.nextLine();

         temp = str.split(" ");

         for(int i = 0; i < temp.length;i++){

             s[i] = Integer.parseInt(temp[i]);

             no[i] = i+1;

         }

         System.out.println("请输入对应编号选手实力值：");

         str = scanner.nextLine();

         temp = str.split(" ");

         for(int i = 0; i < w.length;i++){

             w[i] = Integer.parseInt(temp[i]);

         }

 //        int no[] = new int[]{1,2,3,4};//每个选手的编号，顺序按名次

 //        int s[] = new int[]{7,6,6,7};

 //        int w[] = new int[]{10,5,20,15};

 //        int n = 2;

 //        int r = 4;

 //        int q = 2;

         int i = 0;

         while(i < r){

             i++;

             System.out.println("第"+i+"轮比赛后：");

             obj.sigleAfter(no,s,w);

             for(int t = 0 ; t < s.length;t++){

                 System.out.println("第"+(t+1)+"名:"+no[t]+",分数："+s[t]);

             }

         }

         System.out.println("第"+r+"轮后排名第"+q+"的编号是："+no[q-1]);

     }

     public  void sigleAfter(int no[],int s[],int w[]){

         for(int i = 0; i < s.length-1; i+=2){

             if(w[i] > w[i+1]){

                 s[i] ++;

             }else{

                 s[i+1]++;

             }

         }

         //选择排序

 //        chosesort(s, no, w);

         //快排

         quicksort(s,no,w,0,s.length-1);

     }

     public void chosesort(int s[],int []no,int w[]){

         for(int i = 0; i < s.length-1; i++){

             for(int j = i+1; j< s.length;j++){

                 if(s[i] < s[j]){

                     int temp = s[i];

                     s[i] = s[j];

                     s[j] = temp;

                     temp = no[i];

                     no[i] = no[j];

                     no[j] = temp;

                     temp = w[i];

                     w[i] = w[j];

                     w[j] = temp;

                 }else if(s[i] == s[j]){

                     if(no[i] > no[j]){

                         int temp = s[i];

                         s[i] = s[j];

                         s[j] = temp;

                         temp = no[i];

                         no[i] = no[j];

                         no[j] = temp;

                         temp = w[i];

                         w[i] = w[j];

                         w[j] = temp;

                     }

                 }

             }

         }

     }

     /**

      * 三分取中值策略

      * @param left

      * @param right

      * @return

      */

     public int median3(int s[],int []no,int w[],int left,int right){

         int center = (left+right)/2;

         if(s[left] < s[center]){

             swapReference(no,s,w, center, left);

         }

         if(s[center] < s[right]){

             swapReference(no,s,w, right, center);

         }

         if(s[left] < s[center]){

             swapReference(no,s,w, left, center);

         }

         if(left+1 > right){

             swapReference(no,s,w, center, right);

         }

         return s[right];

     }

     public void quicksort(int []s,int no[],int w[],int left,int right){

         if(left < right){

             int pivot = median3(s,no,w,left,right);

             if(right - left > 1){

                 int i = left;

                 int j = right;

                 while(true){//大的放左边，小的放右边

                     while(s[++i] > pivot){

                         if(s[i] == pivot && no[i] >= no[right]){//积分相同，i的编号较大所以需要移到右边

                             break;

                         }

                     }

                     while(s[--j] <= pivot){

                         if(s[j] == pivot && no[j] <= no[right]){//积分相同，i的编号较小所以需要移到左边

                             break;

                         }

                     }

                     if(i < j){

                         swapReference(s,no,w, i, j);

                     }else{

                         break;

                     }

                 }

                 swapReference(s,no,w, i, right);

                 quicksort(s,no,w, left,i-1);

                 quicksort(s,no,w, i+1, right);

             }

         }

     }

     /**

      * 互换数组中的元素

      * @param a

      * @param i

      * @param j

      */

     private void swapReference(int []no ,int []s,int w[],int i,int j){

         int temp = no[i];

         no[i] = no[j];

         no[j] = temp;

         temp = s[i];

         s[i] = s[j];

         s[j] = temp;

         temp = w[i];

         w[i] = w[j];

         w[j] = temp;

     }

 }