摄影师让 n 名学生站成一排拍合影。
每名学生有一个班号，同班学生互换位置算作同一种站法。
所以一种站法用一个班号序列来表示。
把所有可能的站法按字典序排列。
从前往后比较两种站法，在第一个不同的位置上班号较小的在前。
这个顺序像环一样首尾相接。
最后一种站法（班号始终不增）的下一种是最前面的站法（班号始终不减），最前面的站法的前一种是最后一种站法。
从当前站法出发，m 为正时向下一种站法走 m 次，m 为负时向前一种站法退 −m 次。
m 为 0 时不动。
输出最终到达的站法。
把求下一种站法和求前一种站法分别写成函数，让它们原地修改一个序列。
4 3 1 1 3 2 3 2 3 2 1 3 -1 1 2 2 3 -2 1 3 2
2 1 3 1 3 2 2 2 1 3 2 1
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
求紧接着的下一种站法分三步。
从后往前找第一个满足 a[i] < a[i+1] 的 i，与它后面比 a[i] 大的数中最靠后的 a[j] 交换，然后把从 i+1 到末尾的部分反转。
交换后后面部分总是降序的，所以不用排序，只反转就是最小的形式。
如果没有这样的 i（一路下降），就是最后一种站法，把整个序列反转就是第一种。
求前一种站法要把所有比较反过来：找第一个满足 a[i] > a[i+1] 的 i，与它后面比 a[i] 小的数中最靠后的那个交换，再反转后面部分。
如果没有这样的 i（一路上升），就是第一种站法，把整个序列反转就是最后一种。"只反转一部分"各语言不同。
C++ std::reverse(a.begin() + i + 1, a.end()) 是半开区间，标准库的 std::next_permutation、std::prev_permutation 能整体完成这件事（到达一端时会变成另一端并返回 false）。
C# Array.Reverse(a, 起点, 个数) 的第三个参数是个数，传入末尾下标会越界并抛出 ArgumentException。
Java 的 Collections.reverse(list.subList(i + 1, n)) 会反转原列表，但 int[] 没有这个方法，所以要一边交换两端一边向中间靠拢。
C 也一样。
Craykon 的 列表.反转() 只能反转整个列表，所以区间要用交换两端的 当 循环来反转。
六个陷阱：① Python a[i + 1:].reverse() 和 JS/TS a.slice(i + 1).reverse() 反转的是副本，原来的 a 不变。
Python 要像 a[i + 1:] = a[i + 1:][::-1] 这样放回去。
② 用 a[i] > a[i+1] 来截止上升点的查找，会把相同的班号（2 2）当作上升，班号重复时就会跳过或重复站法。
相等时必须继续往左（>=）；求前一种站法时也一样，相等就继续（<=）。
③ 从 i 后面开始朝末尾方向寻找要交换的数，会与最先遇到的较大数交换，而不是"只大一点点的数"，从而跳过好几种站法。
④ 在最后一种站法时什么都不做，就不会回到第一种。
⑤ 照抄求下一种站法的函数来写前一种，却保留"与较大的数交换"，就会得到错误的站法。
⑥ 只写 for (k = 0; k < m; k++)，m 为负时一次也不会执行。
def next_lineup(a): """a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로).""" i = len(a) - 2 while i >= 0 and a[i] >= a[i + 1]: # 뒤에서부터 처음으로 오르는 곳 i -= 1 if i < 0: # 모두 내려가면 마지막 줄 세우기 → 뒤집으면 첫 줄 세우기 a.reverse() return j = len(a) - 1 while a[j] <= a[i]: # a[i]보다 큰 수 가운데 가장 뒤의 것 j -= 1 a[i], a[j] = a[j], a[i] a[i + 1:] = a[i + 1:][::-1] # 뒤쪽 구간만 제자리에서 뒤집는다 def prev_lineup(a): """a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다.""" i = len(a) - 2 while i >= 0 and a[i] <= a[i + 1]: # 뒤에서부터 처음으로 내려가는 곳 i -= 1 if i < 0: # 모두 오르면 첫 줄 세우기 → 뒤집으면 마지막 줄 세우기 a.reverse() return j = len(a) - 1 while a[j] >= a[i]: # a[i]보다 작은 수 가운데 가장 뒤의 것 j -= 1 a[i], a[j] = a[j], a[i] a[i + 1:] = a[i + 1:][::-1] t = int(input())for _ in range(t): n, m = map(int, input().split()) a = list(map(int, input().split())) step = next_lineup if m > 0 else prev_lineup # m이 음수면 |m|번 앞으로 for _ in range(abs(m)): step(a) print(*a)const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // 구간 [lo, hi]를 제자리에서 뒤집는다function reverseRange(a, lo, hi) { for (; lo < hi; lo++, hi--) [a[lo], a[hi]] = [a[hi], a[lo]];} // a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로)function nextLineup(a) { let i = a.length - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳 if (i < 0) { a.reverse(); // 모두 내려가면 마지막 → 뒤집으면 첫 줄 세우기 return; } let j = a.length - 1; while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것 [a[i], a[j]] = [a[j], a[i]]; reverseRange(a, i + 1, a.length - 1);} // a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다function prevLineup(a) { let i = a.length - 2; while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳 if (i < 0) { a.reverse(); // 모두 오르면 첫 줄 세우기 → 뒤집으면 마지막 return; } let j = a.length - 1; while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것 [a[i], a[j]] = [a[j], a[i]]; reverseRange(a, i + 1, a.length - 1);} let p = 0;const t = data[p++];const out = [];for (let c = 0; c < t; c++) { const n = data[p++]; const m = data[p++]; const a = data.slice(p, p + n); p += n; const step = m > 0 ? nextLineup : prevLineup; // m이 음수면 |m|번 앞으로 for (let k = 0; k < Math.abs(m); k++) step(a); out.push(a.join(" "));}console.log(out.join("\n"));import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // 구간 [lo, hi]를 제자리에서 뒤집는다function reverseRange(a: number[], lo: number, hi: number): void { for (; lo < hi; lo++, hi--) [a[lo], a[hi]] = [a[hi], a[lo]];} // a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로)function nextLineup(a: number[]): void { let i = a.length - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳 if (i < 0) { a.reverse(); // 모두 내려가면 마지막 → 뒤집으면 첫 줄 세우기 return; } let j = a.length - 1; while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것 [a[i], a[j]] = [a[j], a[i]]; reverseRange(a, i + 1, a.length - 1);} // a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다function prevLineup(a: number[]): void { let i = a.length - 2; while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳 if (i < 0) { a.reverse(); // 모두 오르면 첫 줄 세우기 → 뒤집으면 마지막 return; } let j = a.length - 1; while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것 [a[i], a[j]] = [a[j], a[i]]; reverseRange(a, i + 1, a.length - 1);} let p = 0;const t = data[p++];const out: string[] = [];for (let c = 0; c < t; c++) { const n = data[p++]; const m = data[p++]; const a = data.slice(p, p + n); p += n; const step = m > 0 ? nextLineup : prevLineup; // m이 음수면 |m|번 앞으로 for (let k = 0; k < Math.abs(m); k++) step(a); out.push(a.join(" "));}console.log(out.join("\n"));import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { static void swap(int[] a, int x, int y) { int tmp = a[x]; a[x] = a[y]; a[y] = tmp; } // 구간 [lo, hi]를 제자리에서 뒤집는다 static void reverseRange(int[] a, int lo, int hi) { for (; lo < hi; lo++, hi--) swap(a, lo, hi); } // a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로) static void nextLineup(int[] a) { int i = a.length - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳 if (i < 0) { reverseRange(a, 0, a.length - 1); // 마지막 → 뒤집으면 첫 줄 세우기 return; } int j = a.length - 1; while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것 swap(a, i, j); reverseRange(a, i + 1, a.length - 1); } // a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다 static void prevLineup(int[] a) { int i = a.length - 2; while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳 if (i < 0) { reverseRange(a, 0, a.length - 1); // 첫 줄 세우기 → 뒤집으면 마지막 return; } int j = a.length - 1; while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것 swap(a, i, j); reverseRange(a, i + 1, a.length - 1); } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int c = 0; c < t; c++) { StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int[] a = new int[n]; st = new StringTokenizer(in.readLine()); for (int k = 0; k < n; k++) a[k] = Integer.parseInt(st.nextToken()); for (int k = 0; k < m; k++) nextLineup(a); for (int k = 0; k < -m; k++) prevLineup(a); // m이 음수면 |m|번 앞으로 for (int k = 0; k < n; k++) out.append(k > 0 ? " " : "").append(a[k]); out.append('\n'); } System.out.print(out); }}using System;using System.Linq;using System.Text; class Program{ // a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로) static void NextLineup(int[] a) { int i = a.Length - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳 if (i < 0) { Array.Reverse(a); // 마지막 → 뒤집으면 첫 줄 세우기 return; } int j = a.Length - 1; while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것 (a[i], a[j]) = (a[j], a[i]); // Array.Reverse(배열, 시작, 개수) — 셋째 값은 끝 자리가 아니라 개수다 Array.Reverse(a, i + 1, a.Length - (i + 1)); } // a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다 static void PrevLineup(int[] a) { int i = a.Length - 2; while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳 if (i < 0) { Array.Reverse(a); // 첫 줄 세우기 → 뒤집으면 마지막 return; } int j = a.Length - 1; while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것 (a[i], a[j]) = (a[j], a[i]); Array.Reverse(a, i + 1, a.Length - (i + 1)); } static void Main() { int t = int.Parse(Console.ReadLine()!.Trim()); var output = new StringBuilder(); for (int c = 0; c < t; c++) { int[] nm = Console.ReadLine()!.Trim().Split(' ').Select(int.Parse).ToArray(); int[] a = Console.ReadLine()!.Trim().Split(' ').Select(int.Parse).ToArray(); int m = nm[1]; for (int k = 0; k < m; k++) NextLineup(a); for (int k = 0; k < -m; k++) PrevLineup(a); // m이 음수면 |m|번 앞으로 output.Append(string.Join(" ", a)).Append('\n'); } Console.Write(output); }}#include <algorithm>#include <iostream>#include <vector> // a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로)// (표준 라이브러리 std::next_permutation이 바로 이 일을 한다 — 여기서는 직접 쓴다)void nextLineup(std::vector<int>& a) { int i = (int)a.size() - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳 if (i < 0) { std::reverse(a.begin(), a.end()); // 마지막 → 뒤집으면 첫 줄 세우기 return; } int j = (int)a.size() - 1; while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것 std::swap(a[i], a[j]); std::reverse(a.begin() + i + 1, a.end()); // [시작, 끝) 반열린 구간} // a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다// (std::prev_permutation이 이 일을 한다)void prevLineup(std::vector<int>& a) { int i = (int)a.size() - 2; while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳 if (i < 0) { std::reverse(a.begin(), a.end()); // 첫 줄 세우기 → 뒤집으면 마지막 return; } int j = (int)a.size() - 1; while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것 std::swap(a[i], a[j]); std::reverse(a.begin() + i + 1, a.end());} int main() { std::ios::sync_with_stdio(false); int t; std::cin >> t; while (t--) { int n, m; std::cin >> n >> m; std::vector<int> a(n); for (int& x : a) std::cin >> x; for (int k = 0; k < m; k++) nextLineup(a); for (int k = 0; k < -m; k++) prevLineup(a); // m이 음수면 |m|번 앞으로 for (int k = 0; k < n; k++) std::cout << (k ? " " : "") << a[k]; std::cout << '\n'; }}#include <stdio.h> static void swap(int *x, int *y) { int tmp = *x; *x = *y; *y = tmp;} /* 구간 [lo, hi]를 제자리에서 뒤집는다 */static void reverse_range(int *a, int lo, int hi) { for (; lo < hi; lo++, hi--) swap(&a[lo], &a[hi]);} /* a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로) */static void next_lineup(int *a, int n) { int i = n - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; /* 뒤에서부터 처음으로 오르는 곳 */ if (i < 0) { reverse_range(a, 0, n - 1); /* 마지막 → 뒤집으면 첫 줄 세우기 */ return; } int j = n - 1; while (a[j] <= a[i]) j--; /* a[i]보다 큰 수 가운데 가장 뒤의 것 */ swap(&a[i], &a[j]); reverse_range(a, i + 1, n - 1);} /* a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다 */static void prev_lineup(int *a, int n) { int i = n - 2; while (i >= 0 && a[i] <= a[i + 1]) i--; /* 뒤에서부터 처음으로 내려가는 곳 */ if (i < 0) { reverse_range(a, 0, n - 1); /* 첫 줄 세우기 → 뒤집으면 마지막 */ return; } int j = n - 1; while (a[j] >= a[i]) j--; /* a[i]보다 작은 수 가운데 가장 뒤의 것 */ swap(&a[i], &a[j]); reverse_range(a, i + 1, n - 1);} int main(void) { int t; scanf("%d", &t); static int a[1000]; while (t--) { int n, m; scanf("%d %d", &n, &m); for (int k = 0; k < n; k++) scanf("%d", &a[k]); for (int k = 0; k < m; k++) next_lineup(a, n); for (int k = 0; k < -m; k++) prev_lineup(a, n); /* m이 음수면 |m|번 앞으로 */ for (int k = 0; k < n; k++) printf(k ? " %d" : "%d", a[k]); printf("\n"); } return 0;}// 구간 [lo, hi]를 제자리에서 뒤집는다(목록.뒤집기()는 목록 전체만 뒤집는다)구간뒤집기(a, lo, hi){ 当 (lo < hi) { tmp = a[lo]; a[lo] = a[hi]; a[hi] = tmp; lo += 1; hi -= 1; }} // a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로)다음줄(a){ i = a.数量 - 2; 当 (i >= 0 && a[i] >= a[i + 1]) { i -= 1; } 如果 (i < 0) { a.反转(); // 마지막 → 뒤집으면 첫 줄 세우기 返回; } j = a.数量 - 1; 当 (a[j] <= a[i]) { j -= 1; } tmp = a[i]; a[i] = a[j]; a[j] = tmp; 구간뒤집기(a, i + 1, a.数量 - 1);} // a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다앞줄(a){ i = a.数量 - 2; 当 (i >= 0 && a[i] <= a[i + 1]) { i -= 1; } 如果 (i < 0) { a.反转(); // 첫 줄 세우기 → 뒤집으면 마지막 返回; } j = a.数量 - 1; 当 (a[j] >= a[i]) { j -= 1; } tmp = a[i]; a[i] = a[j]; a[j] = tmp; 구간뒤집기(a, i + 1, a.数量 - 1);} t = 控制台.读行().去空白().转数字();循环 (c = 0; c < t; c++){ nm = 控制台.读数字(); a = 控制台.读数字(); m = nm[1]; 循环 (k = 0; k < m; k++) { 다음줄(a); } 循环 (k = 0; k < -m; k++) { 앞줄(a); } 控制台.输出(a.连接(" "));}