C++で配列を一意にするための最小増分
整数Aの配列があるとします。ここでは、移動は任意のA [i]を選択し、それを1ずつインクリメントすることで構成されます。Aのすべての値を一意にするために、移動の最小数を見つける必要があります。したがって、入力が[3,2,1,2,1,7]の場合、出力は6になります。これは、6回移動した後、配列が[3,4,1,2,5,7]になる可能性があるためです。 5回以下の移動で、配列がすべての異なる値を持つことは不可能であることを示すことができます。
これを解決するには、次の手順に従います-
理解を深めるために、次の実装を見てみましょう-
例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minIncrementForUnique(vector<int>& A) {
int ret = 0;
sort(A.begin(), A.end());
set <int> visited;
for(int i = 1; i < A.size(); i++){
if(A[i] <= A[i - 1]){
ret+= (A[i - 1] + 1) - A[i];
A[i] = A[i - 1] + 1;
}
}
return ret;
}
};
main(){
vector<int> v1 = {3,2,1,2,1,7};
Solution ob;
cout << (ob.minIncrementForUnique(v1));
} 入力
[3,2,1,2,1,7]
出力
6
-
配列のGCDをC++でkの倍数にするための最小操作
配列arrと別の値kがあるとします。配列のGCDをkの倍数に等しくするために、最小数の演算を見つける必要があります。この場合、操作は値を増減しています。配列が{4、5、6}のようで、kが5であるとします。4を1増やし、6を1減らすことができるので、5になります。ここでの演算数は2です。 結果を得るには、次の手順に従う必要があります- 手順 − 配列内のすべての要素eについて、手順2と3に従います kの場合、結果を（e mod k）と（k – e mod k）の最小値として増やします。 それ以外の場合、結果は結果+ k – eになります 結果を返す 例 #include <io
-
C++で互いに素な配列を作成するための最小限の挿入
このセクションでは、別の興味深い問題が発生します。 N個の要素の配列があるとします。この配列を互いに素な配列にするためには、交点の最小数を見つける必要があります。互いに素な配列では、2つの連続する要素ごとのgcdは1です。配列も印刷する必要があります。 {5、10、20}のような要素があるとします。これは互いに素な配列ではありません。ここで、5、10、10、20の間に1を挿入すると、互いに素な配列になります。したがって、配列は{5、1、10、1、20}のようになります。 アルゴリズム makeCoPrime(arr, n): begin count := 0 &nb