Niloy007

In Class Assignment On Greedy

May 5th, 2021
736
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int track[130];
  5.  
  6. class Task {
  7.   public:
  8.     char potion;
  9.     int timeNeed;
  10.     int price;
  11. };
  12.  
  13. class sampleInput {
  14.   public:
  15.     char classmate;
  16.     char potionName;
  17.     int lastTime;
  18. };
  19.  
  20. bool compare(Task a, Task b) {
  21.     return (a.price / a.timeNeed) > (b.price / b.timeNeed);
  22. }
  23.  
  24. int main() {
  25.     Task list[] = {
  26.         {'r', 2, 2000},
  27.         {'s', 1, 1000},
  28.         {'t', 1, 4000},
  29.         {'u', 2, 3000},
  30.         {'v', 1, 3000}
  31.     };
  32.  
  33.     int listSize = 5;
  34.     sort(list, list + listSize, compare);
  35.  
  36.     // sampleInput input[] = {
  37.     //  {'a', 'r', 4},
  38.     //  {'b', 's', 1},
  39.     //  {'c', 't', 1},
  40.     //  {'d', 'u', 4},
  41.     //  {'e', 'v', 3}
  42.     // };
  43.  
  44.     sampleInput input[] = {
  45.         {'a', 'r', 4},
  46.         {'b', 's', 5},
  47.         {'c', 't', 1},
  48.         {'d', 'u', 4},
  49.     };
  50.  
  51.     int inputSize = sizeof(input) / sizeof(input[0]);
  52.  
  53.     // Print the input list
  54.  
  55.     // for (int i = 0; i < inputSize; i++) {
  56.     //  cout << input[i].classmate << " " << input[i].potionName << " " << input[i].lastTime << endl;
  57.     // }
  58.  
  59.     int n = 0;
  60.     for (int i = 0; i < inputSize; i++) {
  61.         n = max(n, input[i].lastTime);
  62.     }
  63.  
  64.     Task a[n];
  65.     memset(a, -1, sizeof(a));
  66.  
  67.     for (int i = 0; i < n; i++) {
  68.         a[i].potion = '0';
  69.     }
  70.  
  71.     for (int i = 0; i < listSize; i++) {
  72.         Task temp = list[i];
  73.  
  74.         int cnt = 0;
  75.         int deadline;
  76.         for (int j = 0; j < inputSize; j++) {
  77.             if (temp.potion == input[j].potionName) {
  78.                 deadline = input[j].lastTime;
  79.             }
  80.         }
  81.         deadline--;
  82.  
  83.         if (a[deadline].potion == '0') {
  84.             int cnt = 0;
  85.             for (int j = deadline; j >= 0; j--) {
  86.                 if (a[j].potion == '0') {
  87.                     cnt++;
  88.                 }
  89.                 if (cnt == temp.timeNeed) {
  90.                     break;
  91.                 }
  92.             }
  93.             if (cnt == temp.timeNeed) {
  94.                 int x = 0;
  95.                 for (int j = deadline; j >= 0; j--) {
  96.                     if (a[j].potion == '0') {
  97.                         a[j] = temp;
  98.                         x++;
  99.                         if (x == cnt) {
  100.                             break;
  101.                         }
  102.                     }
  103.                 }
  104.             }
  105.         } else if (a[deadline].potion != '0') {
  106.             bool flag = false;
  107.             for (int j = deadline; j >= 0; j--) {
  108.                 if (a[j].potion == '0') {
  109.                     int cnt = 0;
  110.                     for (int k = j; k >= 0; k--) {
  111.                         if (a[k].potion == '0') {
  112.                             cnt++;
  113.                         }
  114.                         if (cnt == temp.timeNeed) {
  115.                             break;
  116.                         }
  117.                     }
  118.                     if (cnt == temp.timeNeed) {
  119.                         int x = 0;
  120.                         for (int k = j; k >= 0; k--) {
  121.                             a[k] = temp;
  122.                             x++;
  123.                             if (x == cnt) {
  124.                                 flag = true;
  125.                                 break;
  126.                             }
  127.                         }
  128.                     }
  129.                 }
  130.                 if (flag) {
  131.                     break;
  132.                 }
  133.             }
  134.         }
  135.     }
  136.  
  137.     int sum = 0, x = 0;
  138.  
  139.     for (int i = 0; i < n; i++) {
  140.         if (!track[a[i].potion] && a[i].potion != '0') {
  141.             Task ans = a[i];
  142.             for (int j = 0; j < inputSize; j++) {
  143.                 if (a[i].potion == input[j].potionName) {
  144.                     if (x == 0) {
  145.                         cout << input[j].classmate;
  146.                         x = 1;
  147.                     } else {
  148.                         cout << ", " << input[j].classmate;
  149.                     }
  150.                 }
  151.             }
  152.             sum += a[i].price;
  153.             track[a[i].potion] = 1;
  154.         }
  155.     }
  156.     cout << endl;
  157.     cout << sum << endl;
  158. }
  159.  
RAW Paste Data