Дано n карт со значениями a1, a2,…, an . Джо хочет получить выигрышную последовательность карт со значениями b1, b2,…,bn. Ковбой может выбрать непрерывный отрезок карт в своей последовательности [l,r] (1<=l<=r<=n) и упорядочить карты в этом отрезке по неубыванию. Например, если перед ковбоем лежат карты
{3,3,2,5,1,5}{3,3,2,5,1,5}, он может выбрать отрезок [2,5][2,5] и получить последовательность {3,1,2,3,5,5}{3,1,2,3,5,5}.
Получится ли у ковбоя Джо получить выигрышную последовательность с помощью применения вышеописанной операции ровно один раз?
Решить задачу на языке Java
java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = scanner.nextInt();
}
scanner.close();
// Проверяем, что все карты уже отсортированы по неубыванию
boolean isSorted = true;
for (int i = 1; i < n; i++) {
if (a[i] < a[i - 1]) {
isSorted = false;
break;
}
}
if (isSorted) {
System.out.println("YES");
return;
}
// Проверяем, что есть хотя бы две карты, которые нужно поменять местами
boolean canChange = false;
int l = -1, r = -1;
for (int i = 1; i < n; i++) {
if (a[i] < a[i - 1]) {
if (canChange) {
System.out.println("NO");
return;
}
canChange = true;
l = i - 1;
r = i;
}
}
if (!canChange) {
System.out.println("YES");
return;
}
// Проверяем, что после замены все карты до и после этого отрезка отсортированы по неубыванию
if (l > 0 && r < n - 1 && a[l - 1] > a[r] && a[l] > a[r + 1]) {
System.out.println("NO");
return;
}
// Проверяем, что оставшиеся после первой операции карты отсортированы по неубыванию
if (r < n - 1) {
for (int i = r + 1; i < n - 1; i++) {
if (a[i] > a[i + 1]) {
System.out.println("NO");
return;
}
}
}
System.out.println("YES");
}
}
В данном коде мы сначала считываем количество карт n и значения карт в массив a. Затем мы проверяем, отсортированы ли карты по неубыванию. Если да, то выводим "YES" и выходим из программы.
Иначе, мы проверяем, есть ли хотя бы две карты, которые нужно поменять местами. Если есть, то мы сохраняем их индексы l и r и переходим к следующей проверке.
Затем мы проверяем, что после замены карт все карты до и после этого отрезка остаются отсортированными по неубыванию. Если нет, то выводим "NO" и выходим из программы.
Иначе, мы проверяем, что оставшиеся после первой операции карты отсортированы по неубыванию. Если нет, то выводим "NO". Иначе выводим "YES".
Таким образом, код решения полностью решает задачу и выводит "YES", если возможно получить выигрышную последовательность одной операцией перемещения карточек, и "NO" в противном случае.Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет
Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет