Posted By

dirkchang on 02/05/11


Tagged


Versions (?)

Racing Bike Watch (tmp)


 / Published in: C++
 

  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <cstring>
  5.  
  6. typedef std::vector<size_t> RankLevel;
  7.  
  8. int main(int argc, char **argv) {
  9. std::ifstream fin(argv[1]);
  10. size_t n(0), a(0), b(0), sum(0), min(0), tmp_min(0);
  11.  
  12. fin >> n;
  13. min = n;
  14. RankLevel *plist = new RankLevel[n+1];
  15. size_t *conflict_list = new size_t [n+1];
  16. std::memset(conflict_list, 0, sizeof(size_t)*(n+1));
  17. bool *compute_table = new bool [n];
  18. for(size_t i = 0; i < n; ++i) {
  19. fin >> a >> b;
  20. sum = a + b;
  21. if(n > sum) { // valid
  22. plist[n - sum].push_back(a);
  23. }
  24. }
  25.  
  26. for(size_t i = 1; i <= n; ++i) {
  27. std::memset(compute_table, false, sizeof(bool)*n);
  28. for(size_t j = 0; j < plist[i].size(); ++j) {
  29. if(compute_table[plist[i][j]]) {
  30. conflict_list[i]++;
  31. }
  32. else {
  33. compute_table[plist[i][j]] = true;
  34. }
  35. }
  36. tmp_min = n - plist[i].size() - conflict_list[i];
  37. if(min > tmp_min) min = tmp_min;
  38. }
  39.  
  40. std::cout << min << '\n';
  41.  
  42. delete [] compute_table;
  43. delete [] conflict_list;
  44. delete [] plist;
  45. }

Report this snippet  

You need to login to post a comment.