/* 8 6 5 3 1 10 ->分解(a[i], a[i+k], a[i+2k], …と選んでグループiを作る)-> 8 5 1 6 3 10 同じ行の数字同士で交換になる。 -> 各グループで交換回数を独立に最小化すればよい。 グループ内では操作が隣り合った2要素を交換になる。 -> 反転数を考えると、バブルソートが最善! 最初から昇順なら、分解不可だが、-1ではなく0を出力! n % k != 0のときは、分解不可 a[i + m * k]の整列後の場所がa[i + p * k]で表せないときは、交換不可 (m, pは任意の整数。mを最初に固定) それ以外は、分解可能 O(N^2/K) … 計算量が最高に面白いです! */ #include #include #include using namespace std; int n, k; int a[100000]; bool isNg() { int sortedA[1000]; if (n % k != 0) return true; for (int i = 0; i < n; i++) sortedA[i] = a[i]; sort(sortedA, sortedA + n); for (int i = 0; i < n; i++) { int pos = lower_bound(sortedA, sortedA + n, a[i]) - sortedA; if (pos % k != i % k) return true; } return false; } int bubbleSort(vector a) { int i, j, cnt = 0; for (i = 0; i < a.size() - 1; i++) { for (j = a.size() - 1; j > i; j--) { if (a[j-1] > a[j]) { cnt++; swap(a[j-1], a[j]); } } } return cnt; } int main() { int i, j; cin >> n >> k; for (i = 0; i < n; i++) cin >> a[i]; for (i = 0; i < n - 1; i++) if (a[i] > a[i+1]) break; if (i == n - 1) { cout << 0 << endl; return 0; } if (isNg()) { cout << -1 << endl; return 0; } vector arrays[1000]; for (i = 0; i < n; i++) arrays[i % k].push_back(a[i]); int ans = 0; for (i = 0; i < k; i++) { ans += bubbleSort(arrays[i]); } cout << ans << endl; return 0; }