Формируйте все возможные уникальные суммы и все способы их вычисления, выбирая и добавляя элементы из двух массивов. - PullRequest
Новая
       20

Формируйте все возможные уникальные суммы и все способы их вычисления, выбирая и добавляя элементы из двух массивов.

0 голосов
/ 20 января 2019

Даны два массива A и B размера n и m соответственно.Мы можем выбрать элемент из A и один из B такой, что C = Ai + Bj.Мы должны вычислить все возможные пути из суммы C, а также все уникальные суммы.

Ограничения: -

0<A,B<=10^5 // Размер массивов A и B

0<=Ai,Bi<=10^6

Пример ввода / вывода: -

2 3 // Размер массива A и B

5 6 // Элементы массива A

2 2 3 // Элементы массива B

Пример O / P: -

7 2

8 3

9 1

Объяснение: - 7 можно сформировать двумя способами с помощью A1 + B1, A1 + B2 (используя индексирование на основе 1)

8 можно сформировать тремя способами с помощью A1 + B2, A2 + B1, A2+ B2

9 можно сформировать одним способом: A2 + B3

Пожалуйста, помогите мне с решением, меньшим (n * m).

Вот мой код:- 

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,val;
    cin>>n>>m;
    unordered_map<int,int> A;
    unordered_map<int,int> B;
    for(int i=0;i<n;i++)
    {
        cin>>val;
        A[val]++;
    }
    for(int i=0;i<m;i++)
    {
        cin>>val;
        B[val]++;
    }
    map<int,int> ans;
    for(auto it=A.begin();it!=A.end();it++)
    {
        for(auto it1=B.begin();it1!=B.end();it1++)
        {
            ans[it->first+it1->first]+= it->second*it1->second;
        }
    }
    for(auto it=ans.begin();it!=ans.end();it++)
    {
        cout<<it->first<<" "<<it->second<<endl;
    }
}
...