fork(1) download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5. //#include <cstdio>
  6. #include <stdio.h>
  7.  
  8. class Cooperative {
  9. public:
  10.   int q;
  11.   int r;
  12.   int q_lowlimit;
  13.   Cooperative(int q, int r) : q(q), r(r) {}
  14.   ~Cooperative() {}
  15.   friend bool operator<(const Cooperative &a, const Cooperative &b) { return !(a.q < b.q); }
  16.   friend std::ostream &operator<<(std::ostream &s, Cooperative &c) {
  17.     return s << "(" << c.q << "," << c.r << "," << c.q_lowlimit << ")"; }
  18. };
  19.  
  20. void setq_lowlimit(std::vector<Cooperative>&c, int m) {
  21.   int lowlimit = m;
  22.   int i;
  23.   for (i = c.size() - 1; i >= 0; --i) {
  24.     if (lowlimit <= 0)
  25.       break;
  26.     c[i].q_lowlimit = lowlimit;
  27.     lowlimit -= c[i].q;
  28.   }
  29.   if (lowlimit <= 0)
  30.     for (;i >= 0; --i)
  31.       c[i].q_lowlimit = 0;
  32. }
  33.  
  34. void read_data(int &m, int &n, std::vector<Cooperative>&c) {
  35. #define ALPHA 1
  36. #if 0
  37.   std::cin >> m;
  38.   std::cin >> n;
  39.  
  40.   c.reserve(n * ALPHA);
  41.   for (int i = 0; i < n; i++) {
  42.     int q, r;
  43.     std::cin >> q, std::cin >> r;
  44.     c.push_back(Cooperative(q, r));
  45. #else
  46.   scanf("%d", &m);
  47.   scanf("%d", &n);
  48.   c.reserve(n * ALPHA);
  49.   for (int i = 0; i < n; i++) {
  50.     int q, r;
  51.     scanf("%d %d\n", &q, &r);
  52.     c.push_back(Cooperative(q, r));
  53. #endif
  54.   }
  55. }
  56.  
  57. #include <cstdlib>
  58.  
  59. static int const N = 25;
  60. static int const MAX1 = 100;
  61. static int const MAX2 = 10000;
  62.  
  63. static int const seed = 31415926;
  64. void make_data(int &m, int &n, std::vector<Cooperative>&c) {
  65.   srand(seed);
  66.   n = N;
  67.   m = 0;
  68.   c.reserve(n * ALPHA);
  69.   for (int i = 0; i < n; i++) {
  70.     int q, r;
  71.     q = rand() % MAX1 + 1;
  72.     r = rand() % MAX2 + 1;
  73.     m += q;
  74.     c.push_back(Cooperative(q, r));
  75.   }
  76.   m /= 4;
  77. }
  78.  
  79. void dump(int m, int n, std::vector<Cooperative>&c) {
  80.   std::cout << "m = " << m << std::endl;
  81.   std::cout << "n = " << n << std::endl;
  82.   for (size_t i = 0; i < c.size(); i++)
  83.     std::cout << c[i] << ", ";
  84.   std::cout << std::endl;
  85. }
  86.  
  87. /*-----------------------------------------------------------------*/
  88. class Phase {
  89. public:
  90.   int mTotal;
  91.   int rTotal;
  92.   int last_pos;
  93.   Phase(int idx, int q, int r) : mTotal(q), rTotal(r), last_pos(idx) {}
  94.  
  95.   Phase(const Phase *org) {
  96.     this->mTotal = org->mTotal;
  97.     this->rTotal = org->rTotal;
  98.   }
  99.  
  100.   void addCooperative(int idx, int q, int r) {
  101.     this->mTotal += q;
  102.     this->rTotal += r;
  103.     this->last_pos = idx;
  104.   }
  105. };
  106.  
  107. class ComparePriorityA {
  108. public:
  109.   bool operator()(const Cooperative &a, const Cooperative &b) {
  110.     return !(a.q < b.q);
  111.   }
  112. };
  113.  
  114. class ComparePriorityB {
  115. public:
  116.   bool operator()(Phase *a, Phase *b) {
  117.     return !(a->mTotal < b->mTotal);
  118.   }
  119. };
  120.  
  121. void searchPreparation(std::priority_queue<Phase *, std::vector<Phase *>, ComparePriorityB>&q, std::vector<Cooperative>&c) {
  122.   for (int i = 0; i < c.size(); i++)
  123.     q.push(new Phase(i, c[i].q, c[i].r));
  124. }
  125.  
  126. int searchLoop(std::priority_queue<Phase *, std::vector<Phase *>, ComparePriorityB>&q, std::vector<Cooperative>&c, int m) {
  127.   int min_r = 0;
  128.   int t;
  129.   Phase *nowchecking;
  130.   for (int i = 0; i < c.size(); i++) min_r += c[i].r;
  131.   while (!q.empty()) {
  132.     nowchecking = q.top();
  133.     q.pop();
  134. //    std::cout << nowchecking->mTotal << std::endl;
  135.     if (nowchecking->mTotal >= m) {
  136.       if ((t = nowchecking->rTotal) < min_r) {
  137.         min_r = t;
  138.       }
  139.       delete nowchecking;
  140.     } else { /* making child-node and add those to queue and deleted himself */
  141.       for (int i = nowchecking->last_pos + 1; i < c.size(); i++) {
  142.         if (nowchecking->rTotal + c[i].r >= min_r)
  143.           continue;
  144.         if (nowchecking->mTotal + c[i].q < c[i].q_lowlimit)
  145.           continue;
  146.         Phase *Child = new Phase(nowchecking);
  147.         Child->addCooperative(i, c[i].q, c[i].r);
  148.         q.push(Child);
  149.       }
  150.       delete nowchecking;
  151.     }
  152.   } /* !q.empty()? */
  153.   return min_r;
  154. }
  155.  
  156. int searchBestSolution(int m, std::vector<Cooperative>&c) {
  157.   std::priority_queue<Phase *, std::vector<Phase *>, ComparePriorityB> q;
  158.   searchPreparation(/*ref*/q, /*ref*/c);
  159.   return searchLoop(/*ref*/q, /*ref*/c, m);
  160. }
  161.  
  162. /*-----------------------------------------------------------------*/
  163. #include <cassert>
  164. int addCombinationAll(std::vector<int> &c) {
  165.   int n;
  166.   for (n = c.size() - 1; n >= 0; --n) {
  167.     if (!c[n]) {
  168.       c[n] = 1;
  169.       return 0;
  170.     }
  171.     c[n] = 0;
  172.   }
  173.   assert(n < 0);
  174.   return 1;
  175. }
  176.  
  177. int reference(int m, std::vector<Cooperative>&c) {
  178.   std::vector<int> combinationAll(c.size(), 0);
  179.   int min_r;
  180.   for (int i = 0; i < c.size(); i++) min_r += c[i].r;
  181.  
  182.   while (!addCombinationAll(combinationAll)) {
  183.     int rTotal = 0;
  184.     int mTotal = 0;
  185.     for (int i = 0; i < c.size(); i++) {
  186.       if (combinationAll[i]) {
  187.         rTotal += c[i].r;
  188.         mTotal += c[i].q;
  189.       }
  190.     }
  191.     if (mTotal >= m && rTotal < min_r) 
  192.         min_r = rTotal;
  193.   }
  194.   return min_r;
  195. }
  196. /*-----------------------------------------------------------------*/
  197. #include <ctime>
  198. int main() {
  199.   int m, n;
  200.   std::vector<Cooperative> c;
  201.  
  202.   read_data(/*ref*/m, /*ref*/n, /*ref*/c);
  203. //  make_data(m, n, c);
  204.   sort(c.begin(), c.end(), ComparePriorityA());
  205.   setq_lowlimit(/*ref*/c, m);
  206. //  dump(m, n, /*ref*/c);
  207. //  std::cout << reference(m, /*ref*/c) << std::endl;
  208. //  time_t t = time(0);
  209.   std::cout << searchBestSolution(m, /*ref*/c) << std::endl;
  210. //  std::cout << time(0) - t << std::endl;
  211.   return 0;
  212. }
  213. /* end */
  214.  
Success #stdin #stdout 0s 3484KB
comments (?)
stdin 
250
5
35 3640
33 2706
98 9810
57 5472
95 7790
stdout 
23072
https://ideone.com/NV9lu6
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!