1686. 石子游戏 VI

1686. 石子游戏 VI

Alice 和 Bob 轮流玩一个游戏，Alice 先手。

一堆石子里总共有 n 个石子，轮到某个玩家时，他可以 移出 一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。双方都知道对方的评判标准。

给你两个长度为 n 的整数数组 aliceValues 和 bobValues 。aliceValues[i] 和 bobValues[i] 分别表示 Alice 和 Bob 认为第 i 个石子的价值。

所有石子都被取完后，得分较高的人为胜者。如果两个玩家得分相同，那么为平局。两位玩家都会采用 最优策略 进行游戏。

请你推断游戏的结果，用如下的方式表示：

如果 Alice 赢，返回 1 。
如果 Bob 赢，返回 -1 。
如果游戏平局，返回 0 。
1
2
3

示例 1：

输入：aliceValues = [1,3], bobValues = [2,1]
输出：1
解释：
如果 Alice 拿石子 1 （下标从 0开始），那么 Alice 可以得到 3 分。
Bob 只能选择石子 0 ，得到 2 分。
Alice 获胜。

示例 2：

输入：aliceValues = [1,2], bobValues = [3,1]
输出：0
解释：
Alice 拿石子 0 ， Bob 拿石子 1 ，他们得分都为 1 分。
打平。

示例 3：

输入：aliceValues = [2,4,3], bobValues = [1,6,7]
输出：-1
解释：
不管 Alice 怎么操作，Bob 都可以得到比 Alice 更高的得分。
比方说，Alice 拿石子 1 ，Bob 拿石子 2 ， Alice 拿石子 0 ，Alice 会得到 6 分而 Bob 得分为 7 分。
Bob 会获胜。

解代码如下所示：

void quick_sort(int *a,int low,int high,int *b,int *c){
    if(low<high){
        int l=low,h=high;
        int p=a[low],pb=b[low],pc=c[low];

        while(low<high){
            while(low<high&&a[high]<=p){
                high--;

            }
            a[low]=a[high];
            b[low]=b[high];
            c[low]=c[high];

            while(low<high&&a[low]>=p){
                low++;
            }
            a[high]=a[low];
            b[high]=b[low];
            c[high]=c[low];
        }
        a[low]=p;
        b[low]=pb;
        c[low]=pc;
        quick_sort(a,l,low-1,b,c);
        quick_sort(a,low+1,h,b,c);

    }
}

int stoneGameVI(int* aliceValues, int aliceValuesSize, int* bobValues, int bobValuesSize){
    int *rank=(int *)malloc(sizeof(int)*aliceValuesSize);
    for(int i=0;i<aliceValuesSize;i++){
        rank[i]=aliceValues[i]+bobValues[i];
        
    }
    quick_sort(rank,0,aliceValuesSize-1, aliceValues,bobValues);
    int asum=0,bsum=0;
 
     for(int i=0;i<aliceValuesSize;i++){

         if(i%2==0){
          
             int max=aliceValues[i];
             int j=i+1;
            int index=i;
             if(j==aliceValuesSize){
                  asum=asum+aliceValues[i];;
                  break;


             }
             while(rank[j]==rank[i]&&j!=aliceValuesSize){
            
                 if(aliceValues[j]>max){
                     max=aliceValues[j];
                     index=j;

                 }
                 j++;
                   if(j==aliceValuesSize){break;}
             }

             int t=aliceValues[index];
             aliceValues[index]=aliceValues[i];
             aliceValues[i]=t;
             t=bobValues[index];
            bobValues[index]=bobValues[i];
             bobValues[i]=t;





             asum=asum+aliceValues[i];
         }
         else{


              int max=bobValues[i];
             int j=i+1;
           int   index=i;
             if(j==aliceValuesSize){
                  bsum=bsum+bobValues[i];;
                  break;


             }
             while(rank[j]==rank[i]&&j!=aliceValuesSize){
                 if(bobValues[j]>max){
                     max=bobValues[j];
                     index=j;

                 }
                 j++;
                  if(j==aliceValuesSize){break;}
             }
             int t=aliceValues[index];
             aliceValues[index]=aliceValues[i];
             aliceValues[i]=t;
             t=bobValues[index];
            bobValues[index]=bobValues[i];
             bobValues[i]=t;
             bsum=bsum+bobValues[i];

         }

     
    }
    printf("%d %d ",asum,bsum);
    if(asum>bsum){
        return 1;
    }
    if(asum<bsum){
        return -1;
    }
   
    return 0;
  


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123