10 Просмотров

Задание:

Недавно Никита провел очень противоречивый раунд, после которого его вклад очень быстро менялся.

Анонс висел на главной странице n
секунд. В i-ю секунду |ai|-й человек либо поставил лайк, либо убрал лайк (в этой задаче Никите повезло и дизлайков не существует).
Если ai>0, то ai-й человек поставил лайк.
Если ai<0, то −ai человек убрал лайк.
Каждый человек ставил и убирал лайк не более одного раза. Человек не мог убрать лайк, если он до этого его не ставил. Так как после раунда у Никиты вклад стал очень плохим, то он захотел проанализировать, как менялся его вклад, пока анонс был на главной странице. Он обратился к создателю платформы с просьбой дать ему последовательность a1,a2,…,an. Но из-за несовершенства платформы последовательность a перемешалась.

Вам дана перемешанная последовательность a, которая описывает активность пользователей. Вам требуется сказать для каждого момента от 1 до n, какое максимальное и минимальное количество лайков могло быть на посту в этот момент.

Входные данные
В первой строке входных данных дано одно число t (1⩽t⩽1000) — количество наборов входных данных.
В первой строке каждого набора входных данных дано одно число n (1⩽n⩽100) — количество секунд, в течение которых анонс Никиты висел на главной странице.
В следующей строке дано n чисел b1,b2,b3,…,bn (1⩽|bi|⩽n) — перемешанный массив a. Гарантируется, что существует такая перестановка b, что она является корректной последовательностью событий, описанных в условии.

Гарантируется, что сумма n по всем наборам входных данных не превосходит 104.

Выходные данные
Для каждого набора входных данных выведите по две строки, в каждой из которых по n чисел.

В первой строке для каждого набора входных данных выведите максимальное количество лайков, которые Никита мог иметь на анонсе в i-ю секунду.

Во второй строке для каждого набора входных данных выведите минимальное количество лайков, которые Никита мог иметь на анонсе в i-ю секунду. В первом наборе входных данных максимальные значения достигаются при следующей перестановке: 1,2,−2. А минимальные значения при такой: 2,−2,1.

Во третьем наборе входных данных все максимумы достигаются при следующей перестановке: 4,2,3,1,−1,−2. А минимальные значения при следующей перестановке: 2,−2,1,−1,3,4.

Язык программирования C++.

Ответ на задание:

#include <iostream>
#include <vector>

using namespace std;

int main() {
  int t;
  cin >> t;

  while (t--) {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }

    vector<int> mx(n), mn(n);

    int cur_likes = 0;
    mx[0] = cur_likes;
    mn[0] = cur_likes;

    for (int i = 1; i < n; i++) {
      cur_likes += a[i];
      mx[i] = max(mx[i - 1], cur_likes);
      mn[i] = min(mn[i - 1], cur_likes);
    }

    for (int i = 0; i < n; i++) {
      cout << mx[i] << " ";
    }
    cout << endl;

    for (int i = 0; i < n; i++) {
      cout << mn[i] << " ";
    }
    cout << endl;
  }

  return 0;
}

Объяснение:

1. Вводим количество тестовых случаев t.
2. Для каждого тестового случая:
   • Вводим n, длительность отображения анонса.
   • Вводим a, перемешанную последовательность событий.
   • Инициализируем mx и mn для хранения максимального и минимального количества лайков.
   • Инициализируем cur_likes как текущее количество лайков.
   • Для каждого i от 1 до n - 1:
     • Обновляем cur_likes с учетом события a[i].
     • Обновляем mx[i] и mn[i] как максимум/минимум между текущим значением и cur_likes.
   • Выводим mx и mn.

Сложность:

• Время: O(n * t)
• Память: O(n)