TopCoder SRM 701 SortingSubsets
TopCoder Statistics - Problem Statement
This problem is short. Note that we just need to count the count of number's positions to change. We don't care the number of moves we did. So we sort the original array, compare it to the original array. If the number at the same position is not same, we know that that number at the position was changed. So time complexity is O(N).
#include <bits/stdc++.h> using namespace std; class SortingSubsets { public: int getMinimalSize(vector<int> a) { vector<int> c(a); sort(c.begin(), c.end()); int cnt = 0; for (int i = 0; i < int(c.size()); ++i) { cnt += (c[i] == a[i] ? 0 : 1); } return cnt; } }; int main(void) { SortingSubsets a; vector<vector<int> > v(4); v[0] = { 3, 2, 1}; v[1] = {1, 2, 3, 4}; v[2] = {4, 4, 4, 3, 3, 3}; v[3] = {11, 11, 49, 7, 11, 11, 7, 7, 11, 49, 11}; for (auto vv : v) { cout << a.getMinimalSize(vv) << endl; } return 0; }