999ms

1

Jun 15th, 2021
680
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. собес 4
  2. Есть кинотеатр из 1 ряда, в котором n сидений. Некоторые заняты, нужно определить место, которое дальше от всех занятых
  3. /*
  4. int find_seat(const std::vector<int>& row)
  5.  
  6. find_seat(row={1, 0, 0, 0, 1}) -> 2
  7. find_seat(row={1, 0, 1, 0, 0, 1, 0, 0, 0, 1}) -> 2
  8. find_seat(row={1, 0, 1, 0}) -> 1
  9. */
  10.  
  11.  
  12. max(max_first_zeros, max_last_zeros, (max_len + 1) / 2)
  13.  
  14.  
  15.  
  16. int find_seat(std::vector<bool>& row) {
  17.     const int n = row.size();
  18.     int answer = 0;
  19.    
  20.     int cur = 0;
  21.     int prefix_zeros = 0;    
  22.  
  23.     // cur | [i - cur + 1, i] = "0...0"    
  24.     // i = 3
  25.     // cur = 1
  26.     // row[3:3+1] == [False]
  27.    
  28.  
  29.     for (int i = 0; i < n; ++i) {
  30.         if (row[i] == true) {
  31.             cur = 0;
  32.         } else {
  33.             if (cur == i) {
  34.                 prefix_zeros++;    
  35.             }
  36.             cur++;
  37.         }
  38.         answer = max(answer, cur);
  39.     }
  40.    
  41.     answer = std::max({prefix_zeros, (answer + 1) / 2, cur});    
  42.    
  43.     return answer;
  44. }
RAW Paste Data