Python-сообщество

MarinaLunyova · Дек. 9, 2015 14:07:40

Добрый день!
Помогите решить задачу. Даны два массива целых чисел одинаковой длины A и B. Найти индексы таких элементов чтобы их сумма являлась максимально возможной при условии что индекс элемента массива A должен быть меньше или равен индексу элемента массива B.

arr_a = [int(i) for i in input().split()]
arr_b = [int(i) for i in input().split()]
for i in range(0, int(len(arr_a))):
    for j in range(1, int(len(arr_b))):
        if (i<=j):
            if arr_a[i]+arr_b[j]>arr_a[i-1]+arr_b[j-1]:
                print (i,j)

doza_and · Дек. 9, 2015 20:33:32

MarinaLunyova
Помогите решить задачу.

Трудоемкость этой задачи O(n) где n длина массива. Боюсь так у вас задачу не примут.

Отредактировано doza_and (Дек. 9, 2015 20:34:01)

py.user.next · Дек. 10, 2015 04:57:21

doza_and
Трудоемкость этой задачи O(n)

O(n^2)
Там надо брать каждый элемент первого массива и складывать с каждым элементом второго массива. (То, что элемент второго массива должен быть правее, при оценке сложности роли не играет.)

doza_and · Дек. 10, 2015 09:15:37

py.user.next
и складывать с каждым элементом второго массива

:)
Ну может я и ошибаюсь. Идея такая

arr0=[]
arr1=[]
pos0=0
pos11=0
v11=arr1[0]
s=arr0[0]+arr1[0]
for i in range(len(arr0)):
    pos1=0
    v1=arr1[0]
    if arr1[i]>=v1:
        pos1=i
        v1=arr1[i]
    if arr0[i]+v1 >=s:
        pos0=i
        pos11 = pos1
        s=arr0[i]+v1

Это не код это идея.

py.user.next · Дек. 10, 2015 10:53:58

doza_and
Это не код это идея.

Да, что-то непонятное. Давай код, я его поломаю тестами.
Я не знаю, что твой пример вернёт для

1 1 1 1 5 1 1
1 5 1 7 0 0 0

потому что этот пример нельзя запустить, а имена тоже ни о чём определённом не говорят.

По крайней мере, вот это не работает

>>> arr0=[1, 3, 1, 1, 5, 1, 1]
>>> arr1=[1, 5, 1, 7, 0, 0, 0]
>>> pos0=0
>>> pos11=0
>>> v11=arr1[0]
>>> s=arr0[0]+arr1[0]
>>> for i in range(len(arr0)):
...     pos1=0
...     v1=arr1[0]
...     if arr1[i]>=v1:
...         pos1=i
...         v1=arr1[i]
...     if arr0[i]+v1 >=s:
...         pos0=i
...         pos11 = pos1
...         s=arr0[i]+v1
... 
>>> pos0, arr0[pos0]
(3, 1)
>>> pos1, arr1[pos1]
(0, 1)
>>> pos11, arr1[pos11]
(3, 7)
>>>

Отредактировано py.user.next (Дек. 10, 2015 11:00:16)

MarinaLunyova · Дек. 10, 2015 11:16:19

Решила попробовать другой алгоритм, но на каком то тестовом наборе данных есть ошибка.

count = int(input())
arr_a = [int(i) for i in input().split()]
arr_b = [int(i) for i in input().split()]
max_b= max(arr_b)
max_id_b=(arr_b.index(max(arr_b)))
for i in range(0, int(len(arr_a))):
    if (int(len(arr_a)>count) or (int(len(arr_b))>count)):
        print ('Error')
        break
    else:
        if (i<=max_id_b):
            max_a=arr_a[i]+max_b
            if max_a>max_b:
                print (i, max_id_b)
                break
            else: 
                max_b=sorted(set(arr_b))[-2]
                max_id_b=arr_b.index(max_b)

Видимо я что то не понимаю в этой задаче.

Python-сообщество

Уведомления

#1 Дек. 9, 2015 14:07:40

Поиск индексов в массиве

#2 Дек. 9, 2015 20:33:32

Поиск индексов в массиве

#3 Дек. 10, 2015 04:57:21

Поиск индексов в массиве

#4 Дек. 10, 2015 09:15:37

Поиск индексов в массиве

#5 Дек. 10, 2015 10:53:58

Поиск индексов в массиве

#6 Дек. 10, 2015 11:16:19

Поиск индексов в массиве

Board footer