fragment-header
fragment-markdown
홈
로그인
로그아웃
내 블로그
설정
로그인
백준 22172 (C++) Веревочная почта
최초 업로드: 2025-11-05 13:49:59
최근 수정 시간: 2025-11-05 13:49:59
게시자: rlatjwls3333
카테고리: 백준
조회수: 10
# [Bronze I] Веревочная почта [문제 링크](https://www.acmicpc.net/problem/22172) ## 문제 설명 <p>Каждый из нас привык к различным средствам связи: телефон, электронная почта или социальная сеть всегда помогают нам передать другому человеку, возможно, находящемуся на другой стороне Земли, какие-то сведения. В одной известной фирме, предоставляющей в качестве своих сервисов электронную почту и систему мгновенной передачи сообщений, человеку, желающему работать в компании, предлагается следующее тестовое задание: посчитать минимальное время доставки всех сообщений до адресатов с помощью системы, называемой «Веревочная почта».</p> <p>Суть системы сводится к следующему: на одной прямой, вдоль которой натянута веревка, находится <i>n</i> человек, пронумерованных по порядку числами от 1 до <i>n</i>. Известно, что между людьми с номерами, различающимися на 1, больше никого нет, и расстояние между всеми такими соседями одинаково и равно 1 метру.</p> <p>Каждый из них хочет передать одному из других участников системы некоторое сообщение. Так, человек с номером <i>i</i> хочет передать сообщение человеку с номером <i>a<sub>i</sub></i>. Каждый человек закрепляет конверт со своим сообщением на веревке около себя и пишет на нем номер адресата. После этого веревка несколько раз двигается вдоль прямой в разных направлениях, и как только перед человеком оказывается конверт, адресованный ему, он забирает его и получает сообщение.</p> <p>Поскольку веревка двигается с постоянной скоростью, время доставки всех сообщений до адресатов зависит от суммарного расстояния, на которое сдвинется веревка. Задача, предлагаемая кандидату на собеседовании, состоит в минимизации этого расстояния.</p> <p>Например, пусть первый человек хочет отправить сообщение второму, второй — третьему, третий — второму, а четвертый — первому. Тогда необходимо сдвинуть веревку вперед на 1 метр, после этого второй человек получит сообщение от первого, а третий — от второго. После этого веревку необходимо сдвинуть назад на 2 метра (после чего второй получит сообщение от третьего) и еще на 2 (первый получит сообщение от четвертого). Итого, веревку необходимо суммарно передвинуть на 5 метров.</p> ## 입력 <p>Первая строка входных данных содержит одно целое число <i>n</i> (2 ≤ <i>n</i> ≤ 1000) — количество людей, обменивающихся сообщениями. Вторая строка содержит <i>n</i> целых чисел <i>a<sub>i</sub></i> (1 ≤ <i>a<sub>i</sub></i> ≤ <i>n</i>, <i>a<sub>i</sub></i> ≠ <i>i</i>) — номер человека, которому адресовано сообщение <i>i</i>-го участника.</p> ## 출력 <p>Выведите одно целое число — минимальное суммарное расстояние, на которое нужно сдвинуть веревку так, чтобы все сообщения попали по адресу.</p> ## 풀이 왼쪽 끝까지 움직였다가 오른쪽 끝까지 움직이거나, 오른쪽 끝까지 움직였다가 왼쪽 끝까지 움직이는 두 가지 케이스를 확인하면 됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int minVal=INT_MAX, maxVal=INT_MIN; for(int i=1;i<=n;i++) { int val; cin >> val; minVal = min(minVal, val-i); maxVal = max(maxVal, val-i); } int leftCnt = (minVal<0 ? -minVal : 0); int rightCnt = (maxVal>0 ? maxVal : 0); cout << min(leftCnt*2+rightCnt, leftCnt+rightCnt*2); } ```