ทายผลผู้ชนะในภาษา C++

สมมติว่าเรามีอาร์เรย์ของคะแนนที่เป็นจำนวนเต็มไม่ติดลบ ผู้เล่นคนแรกเลือกหนึ่งในตัวเลขจากปลายด้านใดด้านหนึ่งของอาร์เรย์ ตามด้วยผู้เล่นคนที่สอง ตามด้วยผู้เล่นคนแรก เป็นต้น ทุกครั้งที่ผู้เล่นเลือกหมายเลข หมายเลขนั้นจะไม่สามารถใช้กับผู้เล่นอื่นได้ สิ่งนี้จะดำเนินต่อไปจนกว่าจะเลือกคะแนนทั้งหมด ผู้เล่นที่มีคะแนนสูงสุดจะเป็นผู้ชนะ ดังนั้น หากเรามีชุดคะแนน เราต้องทายว่าผู้เล่นที่ 1 เป็นผู้ชนะหรือไม่

ดังนั้นหากอินพุตเป็น [1, 5, 233, 7] เอาต์พุตจะเป็น True ตามที่ผู้เล่นคนแรกเลือก 1 จากนั้นผู้เล่นคนที่สองจะต้องเลือกระหว่าง 5 ถึง 7 ไม่ว่าตัวเลขใดจะเป็นวินาที ผู้เล่นเลือกผู้เล่นคนแรกเลือกได้ 233 สุดท้ายผู้เล่นคนแรกมีคะแนน (234) มากกว่าผู้เล่นคนที่สอง (12) เราจึงต้องคืนค่าจริงเนื่องจากผู้เล่นคนแรกสามารถชนะได้

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ถ้า n เท่ากับ 1 แล้ว −

  • คืนความจริง

• กำหนดเครื่องเล่นอาร์เรย์1 ขนาด:n x n เครื่องเล่นอาร์เรย์2 ขนาด n x n และผลรวมของขนาด n x n

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • ผู้เล่น1[i, j] :=-1

    • ผู้เล่น2[i, j] :=-1

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • สำหรับการเริ่มต้น j :=i เมื่อ j

    • ถ้าฉันเหมือนกับ j แล้ว −

      • sum[i, j] :=arr[i]

    • มิฉะนั้น

      • sum[i, j] :=arr[j] + sum[i, j - 1]

• สำหรับการเริ่มต้นความยาว :=1 เมื่อความยาว <=n อัปเดต (เพิ่มความยาว 1) ทำ -

  • สำหรับการเริ่มต้น i :=0 เมื่อ i + ความยาว - 1

    • จบ :=i + ความยาว - 1

    • ถ้า i + 1 <=สิ้นสุด แล้ว −

      • player1[i, end] :=สูงสุดของ arr[i] + ((ถ้า player2[i + 1 end] เหมือนกับ - 1 แล้ว 0, มิฉะนั้น player2[i + 1, end])) และ arr[end ] + ((ถ้า player2[i, end - 1] เหมือนกับ -1 แล้ว มิฉะนั้น player2[i, end - 1]))

    • มิฉะนั้น

      • player1[i, end] :=arr[i]

    • player2[i, end] :=sum[i, end] - player1[i, end]

• คืนค่า จริง เมื่อ player1[0, n - 1]>=player2[0, n - 1] มิฉะนั้น จะเป็นเท็จ

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   lli solve(vector <int> arr, lli n){
      if (n == 1)
         return true;
      lli player1[n][n], player2[n][n], sum[n][n];
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < n; j++) {
            player1[i][j] = -1;
            player2[i][j] = -1;
         }
      }
      for (int i = 0; i < n; i++) {
         for (int j = i; j < n; j++) {
            if (i == j) {
               sum[i][j] = arr[i];
            }
            else {
               sum[i][j] = arr[j] + sum[i][j - 1];
            }
         }
      }
      for (int length = 1; length <= n; length++) {
         for (int i = 0; i + length - 1 < n; i++) {
            lli end = i + length - 1;
            if (i + 1 <= end)
               player1[i][end] = max(arr[i] + (player2[i + 1][end] == -1 ? 0 : player2[i + 1][end]), arr[end] + (player2[i][end - 1] == -1 ?: player2[i][end - 1]));
            else
               player1[i][end] = arr[i];
               player2[i][end] = sum[i][end] - player1[i][end];
            }
         }
         return player1[0][n - 1] >= player2[0][n - 1];
      }
      bool PredictTheWinner(vector<int>& nums) {
         return solve(nums, nums.size()) ;
   }
};
main(){
   Solution ob;
   vector<int> v = {1, 5, 233, 7};
   cout << (ob.PredictTheWinner(v));
}

อินพุต

{1, 5, 233, 7}

ผลลัพธ์

1