អត្ថន័យនៃជួរនៅក្នុងអារេ


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ Cadence ឥណ្ឌា Expedia FreeCharge GreyOrange Roblox Snapchat Snapdeal អ៊ិនធឺណិតដង។ Yandex
អារេ បញ្ហាសំណួរ

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា“ មធ្យមនៃជួរក្នុងជួរ” ចែងថាអ្នកត្រូវបានផ្តល់ឱ្យ integer អារេ និង q ចំនួនសំណួរ។ សំណួរនីមួយៗមានឆ្វេងនិងស្តាំជាជួរ។ សេចក្តីថ្លែងបញ្ហាស្នើឱ្យស្វែងយល់ថាតើតម្លៃជាន់ស្មើនឹងតម្លៃនៃចំនួនគត់ទាំងអស់ដែលស្ថិតនៅក្នុងជួរដែលបានផ្តល់។

ឧទាហរណ៍

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. ឆ្លងកាត់អារេពី ១ ហើយរក្សាទុកផលបូកនៃតំលៃមុនរបស់ PreMeanSum និងតម្លៃបច្ចុប្បន្ននៃអារេដែលបានផ្តល់ទៅក្នុងតំលៃបច្ចុប្បន្ននៃអារេ PreMeanSum ។
  3. យកទីតាំងខាងឆ្វេងនិងខាងស្តាំនៃសំណួរហើយពិនិត្យមើលថាតើជំហរខាងឆ្វេងដែលបានផ្តល់គឺ ០ ប្រសិនបើពិតបន្ទាប់មកប្រគល់ចំនួនកូតានៃ PreMeanSum [ស្ដាំ] / ស្ដាំ + ១ ។
  4. ផ្សេងទៀតប្រគល់តម្លៃនៃ PreMeanSum [ស្តាំ] -PreMeanSum [ឆ្វេង - 1] / ស្តាំ - ឆ្វេង +1 ។

ការពន្យល់

យើងបានផ្តល់អារេចំនួនគត់និង Q ចំនួនសំណួរ។ ដូច្នេះយើងបានស្នើសុំឱ្យប្រគល់តម្លៃជាន់នៃមធ្យមនៃចំនួនដែលបានមកនៅក្នុងជួរដែលបានផ្តល់ឱ្យ។ ដូច្នេះវិធីសាស្រ្តសាមញ្ញមួយដែលអាចត្រូវបានអនុវត្តតាមសម្រាប់សំណួរនីមួយៗយើងនឹងឆ្លងកាត់អារេពីចំណុចចាប់ផ្តើមនៃជួររហូតដល់ចំណុចបញ្ចប់នៃជួរ។ ហើយទុកផលបូកនៃតម្លៃទាំងអស់ទៅតម្លៃជាក់លាក់។ ឧបមាថាបើយើងត្រូវរកអត្ថន័យ (០, ខ្ញុំ) ។ ដូច្នេះមកដល់ [យើង] យើងនឹងត្រូវបូកសរុបរាល់តំលៃទាំងអស់ពីអារេសូន្យគឺមួយរហូតដល់តម្លៃអ៊ីតដែលបានផ្តល់អោយ។ បន្ទាប់មកយើងនឹងប្រគល់ផលគុណនៃផលបូកនោះនិងចំនួនសរុបនៃតម្លៃដែលបូកនឹងត្រូវបានធ្វើឡើង។

ប៉ុន្តែគុណវិបត្តិមួយនៃនោះគឺយើងត្រូវឆ្លងកាត់ជួរដែលបានផ្តល់សម្រាប់សំណួរនីមួយៗប្រសិនបើយើងមានសំណួរ n ។ វានឹងឆ្លងកាត់ចំនួន n ពេលវេលាប៉ុន្តែវិធីសាស្រ្តដែលយើងកំពុងប្រើវានឹងផ្តល់ចម្លើយនៃសំណួរនីមួយៗក្នុងពេលវេលាថេរបន្ទាប់ពីយើងបានបង្កើតអារេម្តង។

យើងនឹងរៀបចំអារេសម្រាប់អ្វីដែលយើងបានប្រកាសអារេ PreMeanSum ។ បន្ទាប់មកចាប់ផ្តើមធាតុដំបូងនៃអារេ PreMeanSum ជាតម្លៃដំបូងនៃអារេដែលបានផ្តល់។ យើងនឹងឆ្លងកាត់អារេពីមួយទៅប្រវែងនៃអារេគោលបំណងនៃការធ្វើគឺយើងត្រូវទុកផលបូកនៃតម្លៃដែលនៅជាប់គ្នាទៅនឹងតម្លៃបច្ចុប្បន្នខណៈពេលឆ្លងកាត់។ នោះហើយជាមូលហេតុដែលយើងបានចម្លងតម្លៃដំបូងនោះហើយចាប់ផ្តើមពីលេខ ១ ។ យើងនឹងទទួលបានជួរជាចំណុចចាប់ផ្តើមនិងចំណុចបញ្ចប់។ បន្ទាប់ពីនោះយើងនឹងពិនិត្យមើលថាតើតម្លៃខាងឆ្វេងដែលបានផ្តល់ស្មើនឹង ០ ប្រសិនបើពិតបន្ទាប់មកត្រឡប់ការបែងចែករបស់ PreMeanSum [ស្ដាំ] / ស្ដាំ + ១ ដោយគ្រាន់តែបូក / ចំនួនសរុបនៃតម្លៃ។ ក្រៅពីនេះយើងនឹងប្រគល់ការបែងចែកនៃភាពខុសគ្នានៃ PreMeanSum [ស្ដាំ] -PreMeanSum [ឆ្វេង -1] និងស្តាំឆ្វេង + 0 ។ នោះនឹងជាចម្លើយដែលត្រូវការ។

លេខកូដ

កូដ 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

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (n + q) ដែលជាកន្លែងដែល "Q" គឺជាចំនួនសំណួរដែលត្រូវអនុវត្តជាមធ្យមអាចគណនាបាន ឱ (១) ភាពស្មុគស្មាញពេលវេលា។ អូរ (n) ត្រូវមានពេលវេលាដើម្បីភ្ជាប់ PreMeanSum ។

ភាពស្មុគស្មាញនៃលំហ

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។