Open hitolz opened 5 years ago
思路: 先找到最小的位置,记录下来,判断这个位置顺序逆序是否成立。
import java.util.Scanner; public class CF579A { static class Node { int value; int idx; int nextIdx; int preIdx; public int getValue() { return value; } public void setValue(int value) { this.value = value; } public int getIdx() { return idx; } public void setIdx(int idx) { this.idx = idx; } public int getNextIdx() { return nextIdx; } public void setNextIdx(int nextIdx) { this.nextIdx = nextIdx; } public int getPreIdx() { return preIdx; } public void setPreIdx(int preIdx) { this.preIdx = preIdx; } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int q = scanner.nextInt(); for (int i = 0; i < q; i++) { int n = scanner.nextInt(); int[] stu = new int[n]; int minIdx = 0; Node[] nodes = new Node[n]; for (int j = 0; j < n; j++) { int value = scanner.nextInt(); stu[j] = value; if (value < stu[minIdx]) { minIdx = j; } Node node = new Node(); node.value = value; node.idx = j; node.nextIdx = j + 1; node.preIdx = j - 1; if (j == 0) { node.preIdx = n - 1; } if (j == n - 1) { node.nextIdx = 0; } nodes[j] = node; } Node keyNode = nodes[minIdx]; Node minNode = keyNode; Node nextNode = nodes[keyNode.nextIdx]; Node preNode = nodes[keyNode.preIdx]; Node tmp = nextNode; boolean sortClockwise = false; boolean sortCounterclockwise = false; // sortClockwise while (tmp.value < keyNode.value) { keyNode = tmp; tmp = nodes[keyNode.nextIdx]; } if (minNode.value == tmp.value) { sortClockwise = true; } while (tmp.value > keyNode.value) { keyNode = tmp; tmp = nodes[keyNode.nextIdx]; } if (minNode.value == tmp.value) { sortClockwise = true; } keyNode = nodes[minIdx]; minNode = keyNode; tmp = preNode; // sortCounterclockwise while (tmp.value < keyNode.value) { keyNode = tmp; tmp = nodes[keyNode.preIdx]; } if (minNode.value == tmp.value) { sortCounterclockwise = true; } while (tmp.value > keyNode.value) { keyNode = tmp; tmp = nodes[keyNode.preIdx]; } if (minNode.value == tmp.value) { sortCounterclockwise = true; } if (sortClockwise || sortCounterclockwise) { System.out.println("YES"); } else { System.out.println("NO"); } } } }
思路: 先找到最小的位置,记录下来,判断这个位置顺序逆序是否成立。