Решение задачи Парад с Codeforces

Без пояснения   Просмотров: 231

Совсем скоро в Берляндии состоится парад победы над инопланетными захватчиками. К сожалению, в войне погибли все солдаты, и теперь армия состоит исключительно из новобранцев, многие из которых даже не знают, с какой ноги начинается марш. Гражданское население тоже плохо понимает, с какой ноги начинается марш, поэтому важно лишь, чтобы как можно больше солдат шли в одну ногу.

В параде будут принимать участие n пеших колонн, i-я из которых состоит из l i солдат, начинающих марш с левой ноги, и r i солдат, начинающих марш с правой ноги.

Красота парада вычисляется по следующей формуле: если L — это суммарное количество солдат на параде, начинающих марш с левой ноги, а R — это суммарное количество солдат на параде, начинающих марш с правой ноги, то красота будет равна |L - R|.

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

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

Код 

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  int l[n], r[n], lt = 0, rt = 0;
  for (int i = 0; i < n; i++) {
    cin >> l[i] >> r[i];
    lt += l[i];
    rt += r[i];
  }
  int t = abs(lt - rt);
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (t < abs(lt - l[i] + r[i] - rt + r[i] - l[i])) {
      t = abs(lt - l[i] + r[i] - rt + r[i] - l[i]);
      ans = i + 1;
    }
  }
  cout << ans << endl;
  return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 mycod   [email protected]  Карта сайта   Правообладателям