ඔබට ලීට්කෝඩ් විසඳුම ලබා ගත හැකි උපරිම කාසි ගණන


දුෂ්කරතා මට්ටම මධ්යම
වර්ග කිරීම

ගැටළු ප්රකාශය

“ඔබට ලබා ගත හැකි උපරිම කාසි ගණන” යන ගැටලුවේදී අපට කාසි ගොඩවල් 3 * n ලබා දී ඇත. කාසියේ මෙම ගොඩවල් ඔබ සහ ඔබේ මිතුරන් දෙදෙනා වන ඇලිස් සහ බොබ් අතර බෙදා හැරීමට නියමිතය. කාසි ගොඩවල් බෙදා හැරීම සඳහා වන නීති පහත පරිදි වේ.

  1. ඔබ ඕනෑම ගොඩවල් තුනක් තෝරා ගනු ඇත.
  2. මෙම ගොඩවල් 3 න් ඇලිස්ට උපරිම කාසි අඩංගු ගොඩය ලැබේ.
  3. දෙවන උපරිම කාසි අඩංගු ගොඩය ඔබට ලැබෙනු ඇත.
  4. අවම කාසි ගණනක් සහිත ගොඩට බොබ්ට ලැබෙනු ඇත.
  5. සියලුම කාසි ගොඩවල් බෙදා නොහරින තෙක් මෙම පියවර නැවත කරන්න.

ඉහත නීතිරීති අනුගමනය කරමින්, ඔබට ලබා ගත හැකි උපරිම කාසි ගණන අපට සොයාගත යුතුය.

උදාහරණයක්

piles = [9,8,7,6,5,1,2,3,4]
18

පැහැදිලි කිරීම:

ඔබ පහත දැක්වෙන ආකාරයට ගොඩවල් තෝරා ගනු ඇත:

  • (9,8,1)
  • (7,6,2)
  • (5,4,3)

ගොඩවල් තෝරා ගැනීමේ මෙම ක්‍රමය මඟින් කාසි 18 ක් වන උපරිම කාසි සංඛ්‍යාවක් ලබා ගැනීමට ඔබට හැකි වේ.

ඔබට ලීට්කෝඩ් විසඳුම ලබා ගත හැකි උපරිම කාසි ගණන සඳහා ප්‍රවේශය

මෙම ගැටළුව විසඳීම සඳහා සෑම උපක්‍රමයක්ම ගොඩවල් 3 ක් තෝරා ගැනීමේ ක්‍රමයට පිටුපසින් ඇති අතර එමඟින් ඔබට උපරිම කාසි සංඛ්‍යාවක් ලබා ගත හැකිය.

  • බොබ්ට අවම කාසි ගණනක් සහිත ගොඩය ලැබේ. එබැවින් සෑම විටම අවම කාසි ගණන අඩංගු ඉතිරි ගොඩවල් වලින් ගොඩක් තෝරා ගනිමු. 3 * n ගොඩවල් වලින් අවම කාසි ගණනක් සහිත සියලුම ගොඩවල් බොබ්ට ලැබෙන බව එය සහතික කරයි.
  • සෑම අවස්ථාවකදීම උපරිම කාසි ගණන අඩංගු ඉතිරි ගොඩවල් වලින් ගොඩවල් දෙකක් තෝරා ගනිමු. ඇලිස්ට උපරිම කාසි අඩංගු ගොඩය ලැබේ. ඔබට දෙවන උපරිම කාසි ගණන සමඟ ගොඩ ගසයි.
  • උපරිම හා අවම කාසි ගණන සමඟ ගොඩවල් ලබා ගැනීම සඳහා, අපි කරන්නෙමු වර්ග කිරීම අරාව.
  • පහත රූපයේ දැක්වෙන්නේ ඇලිස්, බොබ් සහ ඔබ අතර ගොඩවල් බෙදා හැරීමයි.

ඔබට ලබා ගත හැකි උපරිම කාසි ගණනට ලීට්කෝඩ් විසඳුම

ක්රියාත්මක කිරීම

ඔබට ලබා ගත හැකි උපරිම කාසි ගණන සඳහා C ++ කේතය

#include <bits/stdc++.h> 
using namespace std; 
    int maxCoins(vector<int>& piles) {
     sort(piles.begin(),piles.end());
        int n=piles.size();
        int ans=0;
        for(int i=n/3;i<n;i=i+2)
            ans+=piles[i];
        return ans;
    }
int main() 
{ 
 vector<int> arr = { 9,8,7,6,5,1,2,3,4 }; 
 cout<<maxCoins(arr)<<endl; 
 return 0;
}
18

ඔබට ලබා ගත හැකි උපරිම කාසි ගණන සඳහා ජාවා කේතය

import java.util.Arrays; 
public class Tutorialcup {
    public static int  maxCoins(int[] piles) {
          Arrays.sort(piles);
        int res = 0, n = piles.length;
        for (int i = n / 3; i < n; i += 2)
            res += piles[i];
        return res;
    }
  public static void main(String[] args) {
    int [] arr = {9,8,7,6,5,1,2,3,4}; 
    int ans=  maxCoins(arr);
    System.out.println(ans);
  }
}
18

ඔබට ලීට්කෝඩ් විසඳුම ලබා ගත හැකි උපරිම කාසි සංඛ්‍යාවේ සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඉහත කේතයේ කාල සංකීර්ණතාව වේ ඕ (nlogn) මොකද අපි අරාව වර්ග කරනවා. මෙහි n යනු අරාවේ ප්‍රමාණයයි.

අවකාශයේ සංකීර්ණතාව

ඉහත කේතයේ අවකාශය සංකීර්ණ වේ ඕ (1) මොකද අපි උත්තරය ගබඩා කරන්න විචල්‍යයක් විතරයි පාවිච්චි කරන්නේ.

ආශ්රිත