fork download
copy 
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <string>
  5.  
  6. struct Pair {
  7.     double coeff, cost; 
  8.  
  9.     int id;
  10. };
  11.  
  12.  
  13. // Перебор - возвращает вектор всех последовательностей, дающих максимум:
  14. std::vector<std::vector<int>> brute(const std::vector<Pair>& arr) {
  15.     const int n = (int)arr.size();
  16.     std::vector<int> answ(n); 
  17.     for (int i = 0; i < n; ++i) {
  18.         answ[i] = i;
  19.     }
  20.     double best = -1e9;
  21.     std::vector<std::vector<int>> vars;
  22.     do {
  23.         double temp = 0;
  24.         for (int i : answ) {
  25.             (temp *= arr[i].coeff) -= arr[i].cost;
  26.         }
  27.         if (temp == best) {
  28.             vars.push_back(answ);
  29.         } else if (temp > best) {
  30.             vars.clear();
  31.             vars.push_back(answ);
  32.             best = temp;
  33.         }
  34.     } while (std::next_permutation(answ.begin(), answ.end()));
  35.     return vars;
  36. }
  37.  
  38. // Генерация теста на 10 элементов:
  39. void gen() {
  40.     auto file = fopen("input.txt", "wt");
  41.     fprintf(file, "10 0\n");
  42.     for (int i = 0; i < 10; ++i) {
  43.         double a = 1LL * std::rand() * std::rand() % 10000000 * 1e-6;
  44.         int b = std::rand() % 100 + 1;
  45.         fprintf(file, "%f %d\n", a, b);
  46.     }
  47.     fclose(file);
  48.     std::exit(0);
  49. }
  50.  
  51.  
  52. int main() {
  53.     //gen();
  54.     int n; scanf("%d %*d", &n);
  55.  
  56.     std::vector<Pair> arr(n);
  57.     for (int i = 0; i < n; ++i) {
  58.         scanf("%lf %lf", &arr[i].coeff, &arr[i].cost);
  59.         arr[i].id = i+1;
  60.     }
  61.  
  62.     for (auto& row : brute(arr)) {
  63.         printf("seq: ");
  64.         for (auto& i : row) {
  65.             printf("%d ", i+1);
  66.         }
  67.         printf("\n");
  68.     }
  69.  
  70.     std::stable_sort(arr.begin(), arr.end(), [](const Pair& a, const Pair& b){
  71.         return a.coeff * b.cost - a.cost > b.coeff * a.cost - b.cost;
  72.     });
  73.  
  74.     for (auto& it : arr) {
  75.         printf("%d\n", it.id);
  76.     }
  77.  
  78.     return 0;
  79. }
Success #stdin #stdout 0.15s 4532KB
comments (?)
stdin
copy 
10 0
1.441480 7
8.068210 69
8.948680 72
0.231310 38
6.693760 27
9.012935 15
9.439980 82
7.199010 39
9.643140 91
1.892498 27
stdout
copy 
seq: 6 5 8 3 7 2 9 1 10 4 
6
1
5
8
3
2
7
9
10
4
https://ideone.com/g0vYSq
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!