資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學在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
更新於：2020年8月14日
106 次瀏覽
廣告