fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5. #include <cstdio>
  6.  
  7. class Cooperative {
  8. public:
  9.   int q;
  10.   int r;
  11.   Cooperative(int q, int r) : q(q), r(r) {}
  12.   ~Cooperative() {}
  13.   friend bool operator<(const Cooperative &a, const Cooperative &b) { return !(a.q < b.q); }
  14.   friend std::ostream &operator<<(std::ostream &s, Cooperative &c) { return s << "(" << c.q << "," << c.r << ")"; }
  15. };
  16.  
  17. void read_data(int &m, int &n, std::vector<Cooperative>&c) {
  18. #define ALPHA 1
  19. #if 0
  20.   std::cin >> m;
  21.   std::cin >> n;
  22.  
  23.   c.reserve(n * ALPHA);
  24.   for (int i = 0; i < n; i++) {
  25.     int q, r;
  26.     std::cin >> q, std::cin >> r;
  27.     c.push_back(Cooperative(q, r));
  28. #endif
  29.   scanf("%d", &m);
  30.   scanf("%d", &n);
  31.   c.reserve(n * ALPHA);
  32.   for (int i = 0; i < n; i++) {
  33.     int q, r;
  34.     scanf("%d %d\n", &q, &r);
  35.     c.push_back(Cooperative(q, r));
  36.   }  
  37. }
  38.  
  39. void dump(int m, int n, std::vector<Cooperative>&c) {
  40.   std::cout << "m = " << m << std::endl;
  41.   std::cout << "n = " << n << std::endl;
  42.   for (size_t i = 0; i < c.size(); i++)
  43.     std::cout << c[i] << ", ";
  44.   std::cout << std::endl;
  45. }
  46.  
  47. /*-----------------------------------------------------------------*/
  48. class Phase {
  49. public:
  50.   int mTotal;
  51.   int rTotal;
  52.   int last_pos;
  53.   std::vector<int> combination;
  54.   Phase(int n, int idx, int q, int r) : mTotal(q), rTotal(r) {
  55.     combination.reserve(n);
  56.     last_pos = 0;
  57.     combination[last_pos] = idx;
  58.   }
  59.  
  60.   Phase(int n, const Phase *org) {
  61.     combination.reserve(n);
  62.     this->mTotal = org->mTotal;
  63.     this->rTotal = org->rTotal;
  64.     this->last_pos = org->last_pos;
  65.     for (int i = 0; i <= this->last_pos; i++)
  66.       this->combination[i] = this->combination[i];
  67.   }
  68.  
  69.   void addCooperative(int idx, int q, int r) {
  70.     this->mTotal += q;
  71.     this->rTotal += r;
  72.     this->combination[++last_pos] = idx;
  73.   }
  74. };
  75.  
  76. void searchPreparation(std::queue<Phase *>&q, std::vector<Cooperative>&c) {
  77.   for (int i = 0; i < c.size(); i++)
  78.     q.push(new Phase(c.size(), i, c[i].q, c[i].r));
  79. }
  80.  
  81. int searchLoop(std::queue<Phase *>&q, std::vector<Cooperative>&c, int m) {
  82.   int min_r = 0;
  83.   int t;
  84.   Phase *nowchecking;
  85.   for (int i = 0; i < c.size(); i++) min_r += c[i].r;
  86.   while (!q.empty()) {
  87.     nowchecking = q.front();
  88.     q.pop();
  89.     if (nowchecking->mTotal >= m) {
  90.       if ((t = nowchecking->rTotal) < min_r) {
  91.         min_r = t;
  92.       }
  93.       delete nowchecking;
  94.     } else { /* making child-node and add those to queue and deleted himself */
  95.       for (int i = nowchecking->combination[nowchecking->last_pos] + 1; i < c.size(); i++) {
  96.         if (nowchecking->rTotal + c[i].r >= min_r)
  97.           continue;
  98.         Phase *Child = new Phase(c.size(), nowchecking);
  99.         Child->addCooperative(i, c[i].q, c[i].r);
  100.         q.push(Child);
  101.       }
  102.       delete nowchecking;
  103.     }
  104.   } /* !q.empty()? */
  105.   return min_r;
  106. }
  107.  
  108. int searchBestSolution(int m, std::vector<Cooperative>&c) {
  109.   std::queue<Phase *> q;
  110.   searchPreparation(/*ref*/q, /*ref*/c);
  111.   return searchLoop(/*ref*/q, /*ref*/c, m);
  112. }
  113.  
  114. /*-----------------------------------------------------------------*/
  115. #include <cassert>
  116. int addCombinationAll(std::vector<int> &c) {
  117.   int n;
  118.   for (n = c.size() - 1; n >= 0; --n) {
  119.     if (!c[n]) {
  120.       c[n] = 1;
  121.       return 0;
  122.     }
  123.     c[n] = 0;
  124.   }
  125.   assert(n < 0);
  126.   return 1;
  127. }
  128.  
  129. int reference(int m, std::vector<Cooperative>&c) {
  130.   std::vector<int> combinationAll(c.size(), 0);
  131.   int min_r;
  132.   for (int i = 0; i < c.size(); i++) min_r += c[i].r;
  133.  
  134.   while (!addCombinationAll(combinationAll)) {
  135.     int rTotal = 0;
  136.     int mTotal = 0;
  137.     for (int i = 0; i < c.size(); i++) {
  138.       if (combinationAll[i]) {
  139.         rTotal += c[i].r;
  140.         mTotal += c[i].q;
  141.       }
  142.     }
  143.     if (mTotal >= m && rTotal < min_r) 
  144.         min_r = rTotal;
  145.   }
  146.   return min_r;
  147. }
  148. /*-----------------------------------------------------------------*/
  149. int main() {
  150.   int m, n;
  151.   std::vector<Cooperative> c;
  152.  
  153.   read_data(/*ref*/m, /*ref*/n, /*ref*/c);
  154.   sort(c.begin(), c.end());
  155. //  dump(m, n, /*ref*/c);
  156. //  std::cout << reference(m, /*ref*/c) << std::endl;
  157.   std::cout << searchBestSolution(m, /*ref*/c) << std::endl;
  158.   return 0;
  159. }
  160. /* end */
  161.  
Success #stdin #stdout 0s 3440KB
comments (?)
stdin 
250 
 5 
 35 3640 
 33 2706 
 98 9810 
 57 5472 
 95 7790
stdout 
23072
https://ideone.com/nki5E6
language:
C++ (gcc 8.3)
created:
10 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!