/ Published in: C++
Expand |
Embed | Plain Text
#include <iostream> #include <fstream> #include <vector> #include <cstring> typedef std::vector<size_t> RankLevel; int main(int argc, char **argv) { std::ifstream fin(argv[1]); size_t n(0), a(0), b(0), sum(0), min(0), tmp_min(0); fin >> n; min = n; RankLevel *plist = new RankLevel[n+1]; size_t *conflict_list = new size_t [n+1]; std::memset(conflict_list, 0, sizeof(size_t)*(n+1)); bool *compute_table = new bool [n]; for(size_t i = 0; i < n; ++i) { fin >> a >> b; sum = a + b; if(n > sum) { // valid plist[n - sum].push_back(a); } } for(size_t i = 1; i <= n; ++i) { std::memset(compute_table, false, sizeof(bool)*n); for(size_t j = 0; j < plist[i].size(); ++j) { if(compute_table[plist[i][j]]) { conflict_list[i]++; } else { compute_table[plist[i][j]] = true; } } tmp_min = n - plist[i].size() - conflict_list[i]; if(min > tmp_min) min = tmp_min; } std::cout << min << '\n'; delete [] compute_table; delete [] conflict_list; delete [] plist; }
You need to login to post a comment.
