algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

c.cpp (1995B)


      1 #include <iostream>
      2 #include <vector>
      3 #include <unordered_set>
      4 #include <unordered_map>
      5 #include <algorithm>
      6 #include <queue>
      7 
      8 #define ll long long
      9 
     10 using namespace std;
     11 
     12 int main() {
     13     int testCases, current, eles;
     14     cin >> testCases;
     15 
     16     for(int z = 0; z < testCases; ++z) {
     17         // n books with height arr
     18         // put books in any order I want
     19         // visible from the right if strictly taller than all elements on othe right of it
     20 
     21         // find max number of visible books at a given time
     22         // sum left visible + right visible
     23         
     24         // this has be be ~ linear time (possible sorting)
     25         // can we just sort then alternate?
     26 
     27         // 1 2 2 3 3 3
     28         // 1 2 3 3 3 2
     29         // sum = 5
     30         // print any output that's valid
     31 
     32         cin >> eles;
     33 
     34         vector<int> ls {};
     35         for(int i = 0; i < eles; ++i) {
     36             cin >> current;
     37             ls.push_back(current);
     38         }
     39         
     40 
     41         sort(ls.begin(), ls.end());
     42 
     43         vector<int> fin (ls.size(), 0);
     44 
     45         int left = 0;
     46         int right = ls.size() - 1;
     47         int visible = 0;
     48         
     49         for(int i = 0; i < ls.size(); ++i) {
     50             if(i % 2 == 0) {
     51                 fin[left] = ls[i];
     52                 
     53                 if(left != 0) {
     54                     if(fin[left] > fin[left-1]) {
     55                         visible += 1;
     56                     }
     57                 } else {
     58                     visible += 1;
     59                 }
     60 
     61                 left += 1;
     62             } else {
     63                 fin[right] = ls[i];
     64                 if(right != ls.size() - 1) {
     65                     if(fin[right] > fin[right+1]) {
     66                         visible += 1;
     67                     }
     68                 } else {
     69                     visible += 1;
     70                 }
     71                 right -= 1;
     72             }
     73         }
     74 
     75         cout << visible << endl;
     76         for(int i = 0; i < ls.size(); ++i) {
     77             cout << fin[i] << " ";
     78         }
     79         cout << endl;
     80 
     81         
     82     }
     83 }