在C++中最大化可被K整除的数对个数

任务是计算arr[i] + arr[j]可被K整除的最大数对个数，其中arr[]是一个包含N个整数的数组。

条件是特定索引号不能在多个数对中使用。

输入

arr[]={1, 2 ,5 ,8 ,3 }, K=2

输出 

2

解释 − 期望的数对是：(0,2), (1,3)，因为1+5=6，2+8=10。6和10都可以被2整除。

其他的答案可能是数对：(0,4), (1,3) 或 (2,4), (1,3)，但答案仍然相同，即2。

输入 

arr[]={1 ,3 ,5 ,2 ,3 ,4 }, K=3

输出 

3

下面程序中使用的方法如下

• 在int类型的变量n中存储数组的大小。

• 在MaxPairs()函数中使用无序映射，并为数组的每个元素将um[arr[i]%K]的值增加一。

• 迭代并获取每个可能的um值。

• 如果um值为零，则数对个数将变为um[0]/2。

• 然后可以通过使用(um[a], um[Ka])的最小值，从每个um值'a'中形成数对。

• 从um值中减去使用的数对个数。

示例

 在线演示

#include <bits/stdc++.h>
using namespace std;
int MaxPairs(int arr[], int size, int K){
   unordered_map<int, int> um;
   for (int i = 0; i < size; i++){
      um[arr[i] % K]++;
   }
   int count = 0;
   /*Iteration for all the number that are less than the hash value*/
   for (auto it : um){
      // If the number is 0
      if (it.first == 0){
         //Taking half since same number
         count += it.second / 2;
         if (it.first % 2 == 0){
            um[it.first] = 0;
         }
         else{
            um[it.first] = 1;
         }
      }
      else{
         int first = it.first;
         int second = K - it.first;
         // Check for minimal occurrence
         if (um[first] < um[second]){
            //Taking the minimal
            count += um[first];
            //Subtracting the used pairs
            um[second] -= um[first];
            um[first] = 0;
         }
         else if (um[first] > um[second]){
            // Taking the minimal
            count += um[second];
            //Subtracting the used pairs
            um[first] -= um[second];
            um[second] = 0;
         }
         else{
            //Checking if the numbers are same
            if (first == second){
               //If same then number of pairs will be half
               count += it.second / 2;
               //Checking for remaining
               if (it.first % 2 == 0)
                  um[it.first] = 0;
               else
                  um[it.first] = 1;
            }
            else{
               //Storing the number of pairs
               count += um[first];
               um[first] = 0;
               um[second] = 0;
            }
         }
      }
   }
   return count;
}
//Main function
int main(){
   int arr[] = { 3, 6, 7, 9, 4, 4, 10 };
   int size = sizeof(arr) / sizeof(arr[0]);
   int K = 2;
   cout<<"Maximize the number of sum pairs which are divisible by K is: "<<MaxPairs(arr, size, K);
   return 0;
}

输出

如果我们运行上述代码，我们将得到以下输出：

Maximize the number of sum pairs which are divisible by K is: 3

Sunidhi Bansal

更新于：2020年8月14日

106 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习