질문
10811호: 전복
Duxian에는 총 N개의 바구니가 있으며 각 바구니에는 1부터 N까지 순차적으로 번호가 매겨져 있습니다. 바구니는 일렬로 배열되어 가장 왼쪽 바구니가 첫 번째 바구니이고 다음 바구니가 두 번째 바구니입니다.
www.acmicpc.net
코드
#include <iostream>
#include <vector>
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL); std::cout.tie(NULL);
int n, m;
std::cin >> n >> m;
std::vector<int> arr(n);
for (int i = 0; i < n; ++i) arr(i) = i;
while (m > 0)
{
int i, j;
std::cin >> i >> j;
i--, j--;
for (int k = i; k <= (j + i) / 2; ++k)
{
int v = arr(j - k + i);
arr(j - k + i) = arr(k);
arr(k) = v;
}
m--;
}
for (auto& v : arr) std::cout << v + 1 << " ";
std::cout << "\n";
return 0;
}설명하다
배열을 뒤집을 때의 문제는 전체가 아니라 배열의 일부를 뒤집는 것입니다. 반전을 위해 배열의 모든 범위를 검색할 필요는 없습니다. i에서 (i+j)/2까지 검색하고 값을 변경하면 됩니다.
전체 길이의 절반만 검색하는 이유는 첫 번째 인덱스에서 k번째 값, 마지막 인덱스에서 k번째 값을 변경하기 때문에 사전 검색이 필요하지 않습니다.