fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. int deleteProducts(std::vector<int> ids, int m) {
  6.  std::vector<std::pair<int, int>> ids_counts;
  7.  
  8.  const auto id_comp = [](auto p1, auto p2) { return p1.first <
  9. p2.first; };
  10.  const auto find_element_by_id = [&ids_counts, id_comp](int id) {
  11.  return std::lower_bound(ids_counts.begin(), ids_counts.end(),
  12. std::make_pair(id, 0), id_comp);
  13.  };
  14.  const auto find_or_insert = [&ids_counts, &find_element_by_id,
  15. id_comp](int id, int count) {
  16.  auto it = find_element_by_id(id);
  17.  if (it == ids_counts.end()) {
  18.  it = ids_counts.emplace(ids_counts.end(), id, count);
  19.  std::nth_element(ids_counts.begin(), it,
  20. ids_counts.end(), id_comp);
  21.  it = find_element_by_id(id);
  22.  }
  23.  return it;
  24.  };
  25.  
  26.  for (auto id: ids) {
  27.  const auto it = find_or_insert(id, 0);
  28.  ++it->second;
  29.  }
  30.  
  31.  std::sort(ids_counts.begin(), ids_counts.end(), [](auto p1, auto p2)
  32. { return p1.second > p2.second; });
  33.  
  34. for (const auto& id_count : ids_counts) {
  35. 	std::cout << "id_count " << id_count.first << " " << id_count.second << std::endl;
  36. }
  37.  
  38.  for (auto remaining_removable = m; ids_counts.size() > 0 &&
  39. remaining_removable >= ids_counts.back().second; ) {
  40.  remaining_removable -= ids_counts.back().second;
  41.  ids_counts.pop_back();
  42.  }
  43.  
  44.  return ids_counts.size();
  45. }
  46.  
  47. int main() {
  48. 	std::cout << deleteProducts({3, 3, 2, 1}, 2) << std::endl;
  49. 	return 0;
  50. }
Success #stdin #stdout 0s 4520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
id_count 3 4
1
https://ideone.com/J2oGO4
language:
C++14 (clang 8.0)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!