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<<' ';
}