Guest User

Untitled

a guest
Jan 23rd, 2018
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.25 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <iomanip>
  7. using namespace std;
  8.  
  9. struct quest
  10. {
  11.     int lev;
  12.     bool b;
  13. };
  14.  
  15. bool ls(quest a, quest b)
  16. {
  17.     return a.lev < b.lev;
  18. }
  19.  
  20. int main()
  21. {
  22.     //freopen("input.txt","r",stdin);
  23.     int n,k;
  24.     cin >> n >> k;
  25.     vector<quest> a(n);
  26.     for (int i=0;i<n;++i)
  27.     {
  28.         cin >> a[i].lev;
  29.         a[i].b=1;
  30.     }
  31.     int q;
  32.     cin >>q;
  33.     double mn=2000;
  34.     double mx=-1;
  35.     int tickets_found = 0;
  36.     for (int i=0;i<q;++i)
  37.     {
  38.         int s=0;
  39.         for (int j=0;j<(n/k);++j)
  40.         {
  41.             int h;
  42.             cin >> h;
  43.             if (j==0 && a[h-1].b)
  44.                 ++tickets_found;
  45.             a[h-1].b=0;
  46.             s+=a[h-1].lev;
  47.         }
  48.         double diff = double(s)/(n/k);
  49.         mn = min(mn,diff);
  50.         mx = max(mx,diff);
  51.     }
  52.     if (tickets_found<k) {
  53.         sort(a.begin(),a.end(),ls);
  54.         int i=0;
  55.         int s=0;
  56.         for (int j=0;j<n;j++) {
  57.             if (a[j].b)
  58.             {
  59.                 s+=a[j].lev;
  60.                 ++i;
  61.             }
  62.             if (i>=(n/k)) break;
  63.         }
  64.         double diff = double(s)/(n/k);
  65.         if (i>=n/k)
  66.             mn=min(mn,diff);
  67.  
  68.         i=0;
  69.         s=0;
  70.         for (int j=n-1;j>=0;j--) {
  71.             if (a[j].b)
  72.             {
  73.                 s+=a[j].lev;
  74.                 ++i;
  75.             }
  76.             if (i>=(n/k)) break;
  77.         }
  78.         diff = double(s)/(n/k);
  79.         if (i>=n/k)
  80.             mx=max(mx,diff);
  81.     }
  82.     cout << setprecision (10) <<mn <<' ' <<mx <<endl;
  83. }
Add Comment
Please, Sign In to add comment