Рубрики

Создать массив размером K, который удовлетворяет заданным условиям

При заданных двух целых числах N и K задача состоит в том, чтобы сгенерировать массив arr [] длины K такой, чтобы:

  1. arr [0] + arr [1] +… + arr [K — 1] = N.
  2. arr [i]> 0 для 0 ≤ i <K .
  3. arr [i] <arr [i + 1] ≤ 2 * arr [i] для 0 ≤ i <K — 1 .

Если есть несколько ответов, найдите любой из них, в противном случае выведите -1 .

Примеры:

Input: N = 26, K = 6
Output: 1 2 4 5 6 8
The generated array satisfies all of the given conditions.

Input: N = 8, K = 3
Output: -1

Подход: Пусть r = n — k * (k + 1) / 2 . Если r <0, то ответ уже равен -1 . В противном случае построим массив arr [] , где все arr [i] являются floor (r / k), за исключением крайних правых значений r% k , они ceil (r / k) .
Легко видеть, что сумма этого массива равна r , она отсортирована в неубывающем порядке, а разница между максимальным и минимальным элементом не превышает 1.
Давайте добавим 1 к arr [1] , 2 к arr [2] и так далее (это то, что мы вычитаем из n в
начало).
Тогда, если r! = K — 1 или k = 1, тогда arr [] — наш требуемый массив. В противном случае мы получаем некоторый массив вида 1, 3,… .., arr [k] . Для k = 2 или k = 3 для этого случая нет ответа. В противном случае мы можем вычесть 1 из arr [2] и добавить его к arr [k], и этот ответ будет правильным.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для генерации и печати
// требуемый массив

void generateArray(int n, int k)

{

  

    // Инициализация массива

    vector<int> array(k, 0);

  

    // Нахождение r (подход сверху)

    int remaining = n - int(k * (k + 1) / 2);

  

    // Если r <0

    if (remaining < 0)

        cout << ("NO");

  

    int right_most = remaining % k;

  

    // Поиск значений потолка и пола

    int high = ceil(remaining / (k * 1.0));

    int low = floor(remaining / (k * 1.0));

  

    // Заполняем массив значениями потолка

    for (int i = k - right_most; i < k; i++)

        array[i]= high;

  

    // Заполняем массив значениями пола

    for (int i = 0; i < (k - right_most); i++)

        array[i]= low;

  

    // Добавить 1, 2, 3, ... с соответствующими значениями

    for (int i = 0; i < k; i++)

        array[i] += i + 1;

  

    if (k - 1 != remaining or k == 1)

    {

        for(int u:array) cout << u << " ";

    }

      

    // Нет решения для следующих случаев

    else if (k == 2 or k == 3)

        printf("-1\n");

    else

    {

  

        // Модифицировать A [1] и A [k-1], чтобы получить

        // требуемый массив

        array[1] -= 1;

        array[k - 1] += 1;

        for(int u:array) cout << u << " ";

    }

}

  
// Код драйвера

int main()

{

    int n = 26, k = 6;

    generateArray(n, k);

    return 0;

}

  
// Этот код добавлен
// Мохит Кумар

Джава

// Java реализация подхода

class GFG

{

  
// Функция для генерации и печати
// требуемый массив

static void generateArray(int n, int k)

{

  

    // Инициализация массива

    int []array = new int[k];

  

    // Нахождение r (подход сверху)

    int remaining = n - (k * (k + 1) / 2);

  

    // Если r <0

    if (remaining < 0)

        System.out.print("NO");

  

    int right_most = remaining % k;

  

    // Поиск значений потолка и пола

    int high = (int) Math.ceil(remaining / (k * 1.0));

    int low = (int) Math.floor(remaining / (k * 1.0));

  

    // Заполняем массив значениями потолка

    for (int i = k - right_most; i < k; i++)

        array[i] = high;

  

    // Заполняем массив значениями пола

    for (int i = 0; i < (k - right_most); i++)

        array[i] = low;

  

    // Добавить 1, 2, 3, ... с соответствующими значениями

    for (int i = 0; i < k; i++)

        array[i] += i + 1;

  

    if (k - 1 != remaining || k == 1)

    {

        for(int u:array)

            System.out.print(u + " ");

    }

      

    // Нет решения для следующих случаев

    else if (k == 2 || k == 3)

        System.out.printf("-1\n");

    else

    {

  

        // Модифицировать A [1] и A [k-1], чтобы получить

        // требуемый массив

        array[1] -= 1;

        array[k - 1] += 1;

        for(int u:array) 

            System.out.print(u + " ");

    }

}

  
// Код драйвера

public static void main(String[] args)

{

    int n = 26, k = 6;

    generateArray(n, k);

}
}

  
// Этот код предоставлен PrinciRaj1992

python3

# Python3 реализация подхода

import sys

from math import floor, ceil

  
# Функция для генерации и печати
# обязательный массив

def generateArray(n, k):

  

    # Инициализация массива

    array = [0] * k

      

    # Нахождение г (сверху подход)

    remaining = n-int(k*(k + 1)/2)

  

    # Если г <0

    if remaining<0:

        print("NO")

        sys.exit()

  

    right_most = remaining % k

  

    # Поиск значений потолка и пола

    high = ceil(remaining / k)

    low = floor(remaining / k)

  

    # Заполните массив значениями потолка

    for i in range(k-right_most, k):

        array[i]= high

  

    # Заполните массив значениями пола

    for i in range(k-right_most):

        array[i]= low

  

    # Добавить 1, 2, 3, ... с соответствующими значениями

    for i in range(k):

        array[i]+= i + 1

  

    if k-1 != remaining or k == 1:

        print(*array)

        sys.exit()

  

    # Нет решения для следующих случаев

    elif k == 2 or k == 3:

        print("-1")

        sys.exit()

    else:

  

        # Измените A [1] и A [k-1], чтобы получить

        # обязательный массив

        array[1]-= 1

        array[k-1]+= 1

        print(*array)

        sys.exit()

  
Код водителя

if __name__=="__main__":

    n, k = 26, 6

    generateArray(n, k)

C #

// C # реализация подхода

using System;

  

class GFG

{

  
// Функция для генерации и печати
// требуемый массив

static void generateArray(int n, int k)

{

  

    // Инициализация массива

    int []array = new int[k];

  

    // Нахождение r (подход сверху)

    int remaining = n - (k * (k + 1) / 2);

  

    // Если r <0

    if (remaining < 0)

        Console.Write("NO");

  

    int right_most = remaining % k;

  

    // Поиск значений потолка и пола

    int high = (int) Math.Ceiling(remaining / 

                                 (k * 1.0));

    int low = (int) Math.Floor(remaining / 

                              (k * 1.0));

  

    // Заполняем массив значениями потолка

    for (int i = k - right_most; i < k; i++)

        array[i] = high;

  

    // Заполняем массив значениями пола

    for (int i = 0; 

             i < (k - right_most); i++)

        array[i] = low;

  

    // Добавить 1, 2, 3, ... с

    // соответствующие значения

    for (int i = 0; i < k; i++)

        array[i] += i + 1;

  

    if (k - 1 != remaining || k == 1)

    {

        foreach(int u in array)

            Console.Write(u + " ");

    }

      

    // Нет решения для следующих случаев

    else if (k == 2 || k == 3)

        Console.Write("-1\n");

    else

    {

  

        // Модифицировать A [1] и A [k-1], чтобы получить

        // требуемый массив

        array[1] -= 1;

        array[k - 1] += 1;

        foreach(int u in array)

            Console.Write(u + " ");

    }

}

  
// Код драйвера

public static void Main(String[] args)

{

    int n = 26, k = 6;

    generateArray(n, k);

}
}

  
// Этот код предоставлен PrinciRaj1992

Выход:

1 2 4 5 6 8

Рекомендуемые посты:

Создать массив размером K, который удовлетворяет заданным условиям

0.00 (0%) 0 votes