SHARE
TWEET

Untitled

a guest Apr 19th, 2019 105 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <iostream>
  3. #include <queue>
  4. #include <string>
  5. #include <vector>
  6. #include <random>
  7. #include <iomanip>
  8. using namespace std;
  9. vector<int> r,d,p,w;
  10. int n,t;
  11.  
  12. int F(vector<int> &p2)
  13. {
  14.     int ans = 0;
  15.     for (auto it : p2) {
  16.         ans += w[it];
  17.     }
  18.     return ans;
  19. }
  20.  
  21. int T(vector<int> &p1, int t, int blocked) {
  22.     int tm = t;
  23.     for (auto it:p1) {
  24.         if (it != blocked) {
  25.             if (r[it]>tm)
  26.                 tm = r[it];
  27.             tm += p[it];
  28.         }
  29.     }
  30.     return tm;
  31. }
  32.  
  33. void ConsoleInput()
  34. {
  35.     cerr << "Введите n: ";
  36.     cin >> n;
  37.     cerr << "Введите t: ";
  38.     cin >> t;
  39.     r.resize(n);
  40.     cerr << "Введите r_i: ";
  41.     for (int i = 0; i < n; i++)
  42.         cin >> r[i];
  43.     d.resize(n);
  44.     cerr << "Введите d_i: ";
  45.     for (int i = 0; i < n; i++)
  46.         cin >> d[i];
  47.     p.resize(n);
  48.     cerr << "Введите p_i: ";
  49.     for (int i = 0; i < n; i++)
  50.         cin >> p[i];
  51.     w.resize(n);
  52.     cerr << "Введите w_i: ";
  53.     for (int i = 0; i < n; i++)
  54.         cin >> w[i];
  55. }
  56.  
  57. bool FileInput(const string &path) // считывание с файла
  58. {
  59.     ifstream file_in(path);
  60.     if (!(file_in >> n >> t))
  61.         return false;
  62.     r.resize(n);
  63.     for (int i = 0; i < n; i++)
  64.         if (!(file_in >> r[i]))
  65.             return false;
  66.     d.resize(n);
  67.     for (int i = 0; i < n; i++)
  68.         if (!(file_in >> d[i]))
  69.             return false;
  70.     p.resize(n);
  71.     for (int i = 0; i < n; i++)
  72.         if (!(file_in >> p[i]))
  73.             return false;
  74.     w.resize(n);
  75.     for (int i = 0; i < n; i++)
  76.         if (!(file_in >> w[i]))
  77.             return false;
  78.     return true;
  79. }
  80.  
  81.  
  82.  
  83. pair<vector<int>, vector<int>> FirstModification()
  84. {
  85.     int tk = t;
  86.     vector<int> p1, p2;
  87.     queue<int> nk;
  88.     for (int i = 0; i < n; i++)
  89.         nk.push(i);
  90.     while (!nk.empty()) {
  91.         int i = nk.front();
  92.         if (r[i]>tk)
  93.             tk = r[i];
  94.         if (tk + p[i] <= d[i])
  95.         {
  96.             p2.push_back(i);
  97.             tk += p[i];
  98.             nk.pop();
  99.         } else {
  100.             int ind1 = 0;
  101.             int ind2 = 0;
  102.             p2.push_back(i);
  103.  
  104.             vector<int> cand(p2.size());
  105.             for (int j = 0; j < p2.size(); j++) {
  106.                 cand[j] = T(p2, t, p2[j]);
  107.                 if (cand[ind1] > cand[j]) {
  108.                     ind1 = j;
  109.                 }
  110.                 if (w[p2[ind2]]> w[p2[j]]) {
  111.                     ind2 = j;
  112.                 }
  113.             }
  114.             int m = -1;
  115.             for (int j = 0; j < p2.size(); j++) {
  116.                 if (cand[j]== cand[ind1] && w[p2[j]] == w[p2[ind2]]) {
  117.                     m = j;
  118.                 }
  119.             }
  120.             if (m == -1)
  121.             {
  122.                 m = ind1;
  123.                 for (int j = 0; j < p2.size(); j++)
  124.                     if (cand[j]== cand[m] && w[p2[j]] < w[p2[m]]) {
  125.                         m = j;
  126.                     }
  127.             }
  128.             if (p2[m] == i) {
  129.                 p2.pop_back();
  130.                 p1.push_back(i);
  131.                 nk.pop();
  132.             } else {
  133.                 p2.pop_back();
  134.                 p1.push_back(p2[m]);
  135.                 p2.erase(p2.begin() + m);
  136.                 tk = T(p2, t, -1);
  137.             }
  138.         }
  139.     }
  140.     return {p2, p1};
  141. }
  142.  
  143. pair<vector<int>, vector<int>> SecondModification()
  144. {
  145.     int tk = t;
  146.     vector<int> p1, p2;
  147.     queue<int> nk;
  148.     for (int i = 0; i < n; i++)
  149.         nk.push(i);
  150.     while (!nk.empty()) {
  151.         int i = nk.front();
  152.         tk = max(tk, r[i]);
  153.         if (tk + p[i] <= d[i])
  154.         {
  155.             p2.push_back(i);
  156.             tk += p[i];
  157.             nk.pop();
  158.         } else {
  159.             int ind1 = 0;
  160.             int ind2 = 0;
  161.             p2.push_back(i);
  162.  
  163.             vector<int> cand(p2.size());
  164.             for (int j = 0; j < p2.size(); j++) {
  165.                 cand[j] = T(p2, t, p2[j]);
  166.                 if (cand[ind1] > cand[j]) {
  167.                     ind1 = j;
  168.                 }
  169.                 if (w[p2[ind2]]> w[p2[j]]) {
  170.                     ind2 = j;
  171.                 }
  172.             }
  173.             int m = -1;
  174.             for (int j = 0; j < p2.size(); j++) {
  175.                 if (cand[j]== cand[ind1] && w[p2[j]] == w[p2[ind2]]) {
  176.                     m = j;
  177.                 }
  178.             }
  179.             if (m == -1)
  180.             {
  181.                 m = ind2;
  182.                 for (int j = 0; j < p2.size(); j++) {
  183.                     if (w[p2[j]]== w[p2[m]] &&
  184.                         cand[j]< cand[m]) {
  185.                         m = j;
  186.                     }
  187.                 }
  188.             }
  189.             if (p2[m] == i) {
  190.                 p2.pop_back();
  191.                 p1.push_back(i);
  192.                 nk.pop();
  193.             } else {
  194.                 p2.pop_back();
  195.                 p1.push_back(p2[m]);
  196.                 p2.erase(p2.begin() + m);
  197.                 tk = T(p2, t, -1);
  198.             }
  199.         }
  200.     }
  201.     return {p2, p1};
  202. }
  203. void display(ostream &cout) {
  204.     cout << "N = " << n << " t = " << t << endl;
  205.     cout << "r = ";
  206.     for (int i = 0; i < n; i++)
  207.         cout << r[i] << " ";
  208.     cout << endl;
  209.     cout << "d = ";
  210.     for (int i = 0; i < n; i++)
  211.         cout << d[i] << " ";
  212.     cout << endl;
  213.     cout << "p = ";
  214.     for (int i = 0; i < n; i++)
  215.         cout << p[i] << " ";
  216.     cout << endl;
  217.     cout << "w = ";
  218.     for (int i = 0; i < n; i++)
  219.         cout << w[i] << " ";
  220.     cout << endl;
  221. }
  222.  
  223. void solve(int disp, ostream &cout) {
  224.     auto firstResult = FirstModification();
  225.     cout << "Результат первой модификации";
  226.     cout << endl << "Запаздывающие требования: ";
  227.     for (auto elem : firstResult.second)
  228.         cout << elem + 1 << " ";
  229.  
  230.     cout << endl << "Незапаздывающие требования: ";
  231.     for (auto elem : firstResult.first)
  232.         cout << elem + 1 << " ";
  233.  
  234.     cout << endl <<"Сумма весов запаздывающих требований: " << F(firstResult.second) << endl << endl;
  235.     if (disp) {
  236.         cerr << "Результат первой модификации" << endl;
  237.         cerr << "Запаздывающие требования: ";
  238.         for (auto it : firstResult.second)
  239.             cerr << it + 1 << " ";
  240.  
  241.         cerr << endl << "Незапаздывающие требования: ";
  242.         for (auto it : firstResult.first)
  243.             cerr << it + 1 << " ";
  244.         cerr << endl<<"Сумма весов запаздывающих требований: " << F(firstResult.second) <<
  245.              endl << endl;
  246.     }
  247.     auto secondResult = SecondModification();
  248.     cout << "Результат второй модификации";
  249.  
  250.     cout << endl << "Запаздывающие требования: ";
  251.     for (auto it : secondResult.second)
  252.         cout << it + 1 << " ";
  253.  
  254.     cout << endl <<"Незапаздывающие требования: ";
  255.     for (auto it : secondResult.first)
  256.         cout << it + 1 << " ";
  257.  
  258.     cout << endl<<"Сумма весов запаздывающих требований: " << F(secondResult.second) << endl <<
  259.          endl;
  260.     if (disp) {
  261.         cerr << "Результат второй модификации";
  262.         cerr << endl << "Запаздывающие требования: ";
  263.         for (auto it : secondResult.second)
  264.             cerr << it + 1 << " ";
  265.  
  266.         cerr << endl << "Незапаздывающие требования: ";
  267.         for (auto it : secondResult.first)
  268.             cerr << it + 1 << " ";
  269.         cerr << endl<<"Сумма весов запаздывающих требований: " << F(secondResult.second) <<
  270.              endl << endl;
  271.     }
  272. }
  273.  
  274. void generate_data(int count, int RboderR, int RborderD, int RborderW) // генерация t,r,d,p,w
  275. {
  276.     random_device rd;
  277.     n = count;
  278.     t = rd() % 10;
  279.     r.resize(n);
  280.     d.resize(n);
  281.     p.resize(n);
  282.     w.resize(n);
  283.     for (int i = 0; i < n; i++) {
  284.         d[i] = p[i] = w[i] = r[i] = 0;
  285.         r[i] = rd() % RboderR;
  286.         d[i] = rd() % RborderD;
  287.         while (d[i] <= r[i])
  288.             d[i] = rd() % RborderD + 1;
  289.         w[i] = rd() % RborderW;
  290.     }
  291.  
  292.     sort(d.begin(), d.end());
  293.     sort(r.begin(), r.end());
  294.     for (int i = 0; i < n; i++)
  295.         p[i] = rd() % (d[i] - r[i]) + 1;
  296.     sort(d.begin(), d.end());
  297. }
  298. int best[2];
  299.  
  300. void solveandcompare(int disp, ostream &cout) {
  301.     auto firstResult = FirstModification();
  302.     cout << "Результат первой модификации";
  303.     cout << endl << "Запаздывающие требования: ";
  304.     for (auto elem : firstResult.second)
  305.         cout << elem + 1 << " ";
  306.  
  307.     cout << endl << "Незапаздывающие требования: ";
  308.     for (auto elem : firstResult.first)
  309.         cout << elem + 1 << " ";
  310.  
  311.     cout << endl <<"Сумма весов запаздывающих требований: " << F(firstResult.second) << endl << endl;
  312.     if (disp) {
  313.         cerr << "Результат первой модификации" << endl;
  314.         cerr << "Запаздывающие требования: ";
  315.         for (auto it : firstResult.second)
  316.             cerr << it + 1 << " ";
  317.  
  318.         cerr << endl << "Незапаздывающие требования: ";
  319.         for (auto it : firstResult.first)
  320.             cerr << it + 1 << " ";
  321.         cerr << endl<<"Сумма весов запаздывающих требований: " << F(firstResult.second) <<
  322.              endl << endl;
  323.     }
  324.     auto secondResult = SecondModification();
  325.     cout << "Результат второй модификации";
  326.  
  327.     cout << endl << "Запаздывающие требования: ";
  328.     for (auto it : secondResult.second)
  329.         cout << it + 1 << " ";
  330.  
  331.     cout << endl <<"Незапаздывающие требования: ";
  332.     for (auto it : secondResult.first)
  333.         cout << it + 1 << " ";
  334.  
  335.     cout << endl<<"Сумма весов запаздывающих требований: " << F(secondResult.second) << endl <<
  336.          endl;
  337.     if (disp) {
  338.         cerr << "Результат второй модификации";
  339.         cerr << endl << "Запаздывающие требования: ";
  340.         for (auto it : secondResult.second)
  341.             cerr << it + 1 << " ";
  342.  
  343.         cerr << endl << "Незапаздывающие требования: ";
  344.         for (auto it : secondResult.first)
  345.             cerr << it + 1 << " ";
  346.         cerr << endl<<"Сумма весов запаздывающих требований: " << F(secondResult.second) <<
  347.              endl << endl;
  348.     }
  349.  
  350.     int first = F(firstResult.second);
  351.     int second = F(secondResult.second);
  352.     if (first <=second) {
  353.         best[0]++;
  354.     }
  355.     if (second <= first) {
  356.         best[1]++;
  357.     }
  358. }
  359.  
  360. void Compare_Modifications(ofstream &fout) {
  361.     cerr << "Введите количество задач, на которых будут сравниваться алгоритмы: ";
  362.     int tests;
  363.     cin >> tests;
  364.     cerr << "Введите n: ";
  365.     int count;
  366.     cin >> count;
  367.     int rboderR, rborderD, rborderW;
  368.     cerr << "Введите максимальную границу r_i: ";
  369.     cin >> rboderR;
  370.     cerr << "Введите максимальную границу d_i: ";
  371.     cin >> rborderD;
  372.     cerr << "Введите максимальную границу w_i: ";
  373.     cin >> rborderW;
  374.     int disp = 2;
  375.     while (disp != 0 && disp != 1) {
  376.         cerr << "Для просмотра решения каждого примера нажмите 1, иначе 0: ";
  377.         cin >> disp;
  378.     }
  379.  
  380.     best[0] = best[1] = 0;
  381.     for (int i = 0; i < tests; i++) {
  382.         generate_data(count, rboderR, rborderD, rborderW);
  383.         display(fout);
  384.         if (disp)
  385.             display(cerr);
  386.         solveandcompare(disp, fout);
  387.     }
  388.     cerr << fixed << setprecision(2) << "Первая модификация не хуже второй в " << best[0] * 100.0 / tests << " % задач\n";
  389.     cerr << fixed << setprecision(2) << "Вторая модификация не хуже первой в " << best[1] * 100.0 / tests << " % задач\n";
  390. }
  391.  
  392. int main() {
  393.     ofstream fout("result.txt");
  394.     bool ok = true;
  395.     while (ok) {
  396.         int choise = -1;
  397.         while (choise < 0 || choise > 3) {
  398.             cerr << "Введите 1 для ввода данных с файла" << endl;
  399.             cerr << "2 для ввода данных с консоли" << endl;
  400.             cerr << "3 для сравнения модификаций" << endl;
  401.             cerr << "0 для выхода из программы" << endl;
  402.             cin >> choise;
  403.  
  404.         }
  405.         switch (choise) {
  406.             case 1: {
  407.                 cerr << "Введите путь к файлу: ";
  408.                 string path;
  409.                 cin >> path;
  410.                 if (!FileInput(path)) {
  411.                     cerr << "Не удалось открыть файл или неверные входные данные в файле" << endl;
  412.                 } else {
  413.                     display(cerr);
  414.                     solve(1, fout);
  415.                 }
  416.                 break;
  417.             }
  418.             case 2: {
  419.                 ConsoleInput();
  420.                 solve(1, fout);
  421.                 break;
  422.             }
  423.             case 3:{
  424.                 Compare_Modifications(fout);
  425.                 break;
  426.             }
  427.             case 0: {
  428.                 ok = false;
  429.                 break;
  430.             }
  431.         }
  432.     }
  433. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top