08-15 360筆試題目第二題

題目兩個數字，n位數，m進制，可以重新排序數字的順序，兩個數對應相加并對m取模而不進位，求最大和

例如輸入

5 5

4 4 1 1 1

4 3 0 1 2

5 5 代表兩個數都有5位（個 十 百 千 萬…），後面那個5代表5進制

4 4 1 1 1 代表第一個數，每位之間加空格隔開

4 3 0 1 2 代表第二個數，

連個數各位上的數都是正整數，且可以重新排列，問兩個數對應相加并對m取模而不進位的最大值

輸出結果為

4 4 3 3 2

過程

4 4 1 1 1 -------> 1 4 1 4 1

4 3 0 1 2 -------> 3 0 2 4 1

結果4 4 3 8 2，對5取模得到 4 4 3 3 2

思路

1、對兩個數組的數求餘

2、将其中一個數組的元素放到哈希表中 B，這樣查找會比暴力解法少一層循環

3、從num=m-1開始在哈希表B中找

與A[i]和為num的元素在哈希表B中是否存在，存在，就對和m求餘存在A[i]中，然後A[i]設定為已經處理了

注意這裡的num如果比A[i]大的話，要加上一個進制m

不知道過沒過，同學沒打完

代碼

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
   int n,m;
   cin>>n>>m;
   vector<int> A(n,0);
   vector<bool> sA(n,false);
   unordered_map<int,int> B;
   int value;
 
   for(int i=0;i<n;i++)
   {
       cin>>A[i];
       A[i]=A[i]%m;
 
   }
   for(int i=0;i<n;i++)
   {
       cin>>value;
       value=value%m;
       B[value]++;
   }
 
   int num=m;
   while(m--)          //從最大的數m-1開始找
   {
       if(!B.size())        //當哈希表中沒有元素了，說明已經找完了
           break;
 
       for(int i=0;i<n;i++)
       {
           if(sA[i])
                continue;   //對已經比對好的A中的元素，不需要在比對了
 
           int temp=m;
           if(m<A[i])            //如果m的值小于A[i]，那麼m-A[i]就是負數，肯定不行
               temp=m+num;
 
           if(B[temp-A[i]]>=1)       //與A[i]和為num的元素在哈希表B中是否存在，存在，就對和m求餘存在A[i]中，然後A[i]設定為已經處理了
           {
               B[temp-A[i]]--;
               A[i]=temp%num;
               sA[i]=true;
           }
       }
   }
   sort(A.begin(),A.end(),[](int a,int b){return a>b;});
   for(auto c:A)
      cout<<c<<' ';
}