牛客筆試題

今天，Alice 和 Bob 兩個人發明瞭一個新的取石子游戲。我們將 n 枚石子擺放成一行，從左到右每枚石子有兩個參數，能量ei 和得分ai 。Alice 和 Bob 兩人輪流決策，從左到右依次取石子，Alice 先手。每個回合，玩家可以選擇下列兩個操作之一：1. 消耗一個單位的能量，跳過這個回合。2. 取當前位置的石子。初始時，Alice 和 Bob分別有A和B單位的能量，兩個玩家的目的都是最大化自己的得分，雙方都採取最優決策，問游戲結束時，Alice 和 Bob 的得分分別為多少。

題目給定A和B(0≤A≤10^9,0≤B≤10^9)同時給定石子個數n(1≤n≤100), 從左向右,每顆石子的能量e和得分a(所有數字均為正整數，e中元素均小於等於10^9,a中元素的和小於等於100)。請返回一個數組，其中第一個元素為Alice的得分，第二個元素為Bob的得分。

9,0,7,[66,2,6,2,8,4,3],[7,12,65,7,4,40,15]

返回：[112,38]

#include<vector>
class GetT
{
public:
    //目的，最大化自己的得分
    void Get(int &A, int &B, int N, int *e, int *a,int re[])
    {
        //先手
        int *pCurPer = &A;
        int curPer = 1;


        int  cur = 0;
        while (cur<N)
        {
            //有能量且判定下回合的更值錢
            //if (Magic() && NextIsBetter())
            if (*pCurPer && a[cur+1]>a[cur])
            {
                (*pCurPer)--;
                GetNext(pCurPer, curPer, A, B);
                continue;
            }
            else
            {
                //獲取能量，獲取得分。
                *pCurPer += e[cur];
                re[curPer] += a[cur];

                GetNext(pCurPer, curPer, A, B);
                cur++;
            }
            //取當前位置的石子。
        }
    }
    void GetNext(int *&cur,int &curper,int &p,int &q)
    {
        curper = !curper;
        if (cur == &p)
        {
            cur = &q;
        }
        else
        {
            cur = &p;
        }
    }
};

測試：

void main()
{
    int A = 9;
    int B = 0;
    const int s = 7;
    int see[] = { 66, 2, 6, 2, 8, 4, 3 };
    int sea[] = { 7, 12, 65, 7, 4, 40, 15 };

    int re[] = {0,0};
    GetT get;

    get.Get(A, B, s, see, sea,re);
    cout << re[0] << "\t";
    cout << re[1] << endl;
}

運行結果

112 38
請按任意鍵繼續. . .