በሰልፍ ውስጥ የክልል አማካይ  


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ ካዴንስ ህንድ Expedia ፍሪጅ ቻርጅ ግሬይ ብርቱካናማ Roblox Snapchat Snapdeal ታይምስ በይነመረብ Yandex
ሰልፍ የጥያቄ ችግር

የችግሩ መግለጫ  

“በክልል ውስጥ ያለው አማካይ መጠን” ችግሩ “አንድ” እንደተሰጠ ይገልጻል ኢንቲጀር ደርድር እና q የጥያቄዎች ብዛት። እያንዳንዱ ጥያቄ ግራ እና ቀኝ እንደ ክልል ይ containsል። የችግሩ መግለጫ በተጠቀሰው ክልል ውስጥ የሚመጡትን የሁሉም ቁጥሮች ወለል ዋጋ ለማወቅ ይፈልጋል።

ለምሳሌ  

array[] = {2, 5, 1, 6, 7, 8}

Query: {(1, 4), (0,2), (4,5)}
4 2 7

ማስረጃ

(1,4) ስለዚህ አማካይ ዋጋ 5,1,6,7 ይህም 4 ነው

(0,2) ስለዚህ አማካይ ዋጋ 2,5,1 ይህም 2 ነው

(4,5) ስለዚህ አማካይ ዋጋ 7,8 ይህም 7 ነው

በሰልፍ ውስጥ የክልል አማካይ

 

አልጎሪዝም  

  1. አንድ ድርድር PreMeanSum ይፍጠሩ እና እንደ የተሰጠው ድርድር ዋጋ የመጀመሪያ ዋጋውን ያስጀምሩ።
  2. ድርድሩን ከ 1 በማለፍ የቀደመውን የ ‹PreMeanSum› ድምር ድምር እና የተሰጠው ድርድር የአሁኑ ዋጋ ወደ የአሁኑ የ ‹PreMeanSum› ድርድር እሴት ያከማቹ ፡፡
  3. የግራውን እና የቀኙን ቦታ ያግኙ እና የግራ ቦታ ከተሰጠ 0 ከሆነ ያረጋግጡ ፣ እውነት ከሆነ የቅድመ መአንሱም [ቀኝ] / የቀኝ + 1 ተከራካሪውን ይመልሱ።
  4. ሌላ የ PreMeanSum [ቀኝ] -PreMeanSum [ግራ - 1] / ቀኝ - ግራ +1 ዋጋን ይመልሱ።

ማስረጃ

የኢንቲጀር ድርድር እና የ q ብዛት ጥያቄዎችን ሰጥተናል። ስለዚህ በተጠቀሰው ክልል ውስጥ ለሚመጡት የቁጥሮች አማካይ የወለል ዋጋ እንዲመለስ ጠይቀናል ፡፡ ስለዚህ እንደ እያንዳንዱ ጥያቄ ሊከተል የሚችል ቀላል አቀራረብ ከክልል መነሻ ቦታ እስከ ክልሉ መጨረሻ ድረስ ድርድርን እናቋርጣለን ፡፡ እና የሁሉም እሴቶች ድምር ወደ አንድ የተወሰነ እሴት ያከማቹ። የ (0, i) አማካይ መፈለግ ካለብን እንበል ፡፡ ስለዚህ ያ አር [i] ፣ ሁሉንም እሴቶች ከድርድር ዜሮ አንድ እስከ አንድ እስከ ተሰጠው እሴት ዋጋ ማጠቃለል አለብን። ከዚያ የዚያን ድምር ድርሻ እና አጠቃላይ እሴቶችን እንመልሳለን ፣ የትኛው ድምር ተሰራ።

ተመልከት
የሚቀጥለው የበለጠ ድግግሞሽ ንጥረ ነገር

ነገር ግን የዚያ አንዱ ኪሳራ n እኛ መጠይቆች ካሉን ለእያንዳንዱ ጥያቄ ለተሰጠው ክልል መሻገር አለብን ፡፡ የ n ን ቁጥር ያቋርጣል ፣ ግን የምንጠቀመው አቀራረብ ድርድርን ከገነባን በኋላ የእያንዳንዱን ጥያቄ መልስ በቋሚነት ይመልሳል።

እኛ የቅድመ መአንሱም ድርድርን ስለ አውጀን ድርሱን እንገነባለን። ከዚያ የ ‹PreMeanSum› ድርድር የመጀመሪያውን ንጥረ ነገር እንደ የተሰጠው ድርድር የመጀመሪያ እሴት ያስጀምሩ ፡፡ አደረጃጀቱን ከአንድ እስከ ድርድሩ ርዝመት ድረስ እናልፋለን ፣ ይህን ለማድረግ ዓላማችን በሚጓዙበት ጊዜ ሁለት ተጓዳኝ እሴቶችን አሁን ካለው እሴት ጋር ማከማቸት አለብን ፡፡ ለዚያም ነው ያንን የመጀመሪያ እሴት ቀድተን ከ 1. ጀምሮ ክልሉን እንደ መነሻ እና እንደ መጨረሻ ነጥብ እንቀበላለን ፡፡ ከዚያ በኋላ የተሰጠው የግራ እሴት ከ 0 ጋር እኩል መሆኑን እናረጋግጣለን ፣ እውነት ከሆነ ፣ ከዚያ የ PreMeanSum [ቀኝ] / ቀኝ + 1 ክፍፍልን በቀላል ድምር / አጠቃላይ ዋጋዎች ይመልሱ። ያለበለዚያ የ PreMeanSum [ቀኝ] -PreMeanSum [ግራ -1] እና ቀኝ-ግራ + 1 የልዩነት ክፍፍልን እንመልሳለን። ያ የሚፈለገው መልስ ይሆናል ፡፡

ኮድ  

በሰልፍ ውስጥ መካከለኛ ክልል ለማግኘት የ C ++ ኮድ

#include<iostream>
#include<math.h>

#define MAX 1000005
using namespace std;

int PreMeanSum[MAX];

void buildPreMean(int arr[], int n)
{
    PreMeanSum[0] = arr[0];
    for (int i = 1; i < n; i++)
        PreMeanSum[i] = PreMeanSum[i - 1] + arr[i];
}

int getMeanInRange(int l, int r)
{
    if (l == 0)
        return floor(PreMeanSum[r] / (r + 1));

    return floor( (PreMeanSum[r] - PreMeanSum[l - 1]) / (r - l + 1));
}

int main()
{

    int arr[] = {2,5,1,6,7,8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    buildPreMean(arr, n);
    cout << getMeanInRange(1, 4) << endl;
    cout << getMeanInRange(0, 2) << endl;
    cout << getMeanInRange(4, 5) << endl;
    return 0;
}
4
2
7

የጃቫ ኮድ በሠልፍ ውስጥ መካከለኛ ክልል ለማግኘት

class MeanInRange
{
    public static final int MAX = 1000005;

    static int PreMeanSum[] = new int[MAX];

    static void buildPreMean(int arr[], int n)
    {
        PreMeanSum[0] = arr[0];
        for (int i = 1; i < n; i++)
            PreMeanSum[i] = PreMeanSum[i - 1] + arr[i];
    }

    static int getMeanInRange(int l, int r)
    {
        if (l == 0)
            return (int)Math.floor(PreMeanSum[r] / (r + 1));

        return (int)Math.floor((PreMeanSum[r] -
                                PreMeanSum[l - 1]) / (r - l + 1));
    }

    public static void main(String[] args)
    {
        int arr[] = {2,5,1,6,7,8 };
        int n = arr.length;
        buildPreMean(arr, n);
        System.out.println(getMeanInRange(1, 4));
        System.out.println(getMeanInRange(0, 2));
        System.out.println(getMeanInRange(4, 5));
    }
}
4
2
7

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ኦ (n + q) የት "Q" በ ውስጥ ሊሰላ ስለሚችል የሚከናወኑ የጥያቄዎች ብዛት ነው ኦ (1) የጊዜ ውስብስብነት. ሆይ (n) የ ‹PreMeanSum› ን ቀድመው ለመቁጠር ጊዜ ያስፈልጋል ፡፡

ተመልከት
በተደረደሩ በተዞረ ድርድር ውስጥ ይፈልጉ

የቦታ ውስብስብነት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው።