给定一个大小为 n 的整数数组 arr[]，我们的任务是检查是否可以通过执行任意次数的以下两种类型的操作，将给定的数组排序为非递减顺序（即 arr[i] ≤ arr[i+1]）：
- 你可以从 1 到 n-1（使用 1-based 索引）中选择任意索引，并将 arr[i] 和 arr[i+1] 增加任意正数。
- 你可以从 1 到 n-1 中选择任意索引，并将 arr[i] 和 arr[i+1] 减少任意正数。
> 注意： 数组元素在任何时候都可以是负数。
示例：
> 输入: arr[] = {6, 4, 3, 5, 2 }
> 输出: YES
> 解释:
>
> – 在索引 1 上执行类型-2 操作并选择 4，现在数组变为- {2, 0, 3, 5, 2}
> – 在索引 3 上执行类型-2 操作并选择 4，现在数组变为 {2, 0, -1, 1, 2}
> – 在索引 2 上执行类型-1 操作并选择 2，现在数组变为 {2, 2, 1, 1, 2}
> – 在索引 3 上执行类型-1 操作并选择 1，现在数组变为 {2, 2, 2, 2, 2}
>
> 现在数组 {2, 2, 2, 2, 2} 已经是排序状态。
>
> 输入: arr[] = {3, 1, 5, 4 }
> 输出: NO
> 解释: 如果我们使用类型-1 操作轻易地使 arr[] = {3, 3, 3, 0}，现在不可能让数组有序，因为我们无法对最后一个索引执行操作。
方法思路： 要解决这个问题，请遵循以下思路：
> – 如果 n 是奇数，答案永远是“是”。
> – 让我们证明一下：我们将从索引 2 开始到 n-1，尝试使 arr[i] 等于 arr[i-1]，但我们不能对最后一个索引执行操作。因此，执行操作后，我们的数组将像这样 {x, x….., x, y }。y 可以等于 x。但如果 y 不等于 x，我们可以通过从初始索引开始配对并执行操作来使所有数组元素相等，像这样 {x, x, x, x, y}。执行操作后，我们的数组将像这样 {x, x ….., x, x }，这是已排序的。
> – 如果 n 是偶数，我们将从索引 2 开始迭代到 n-1，并尝试通过使用增加或减少操作使 arr[i] 等于 arr[i-1]。最后，检查是否
> arr[n-1] ≤ arr[n]，如果满足这个条件，答案将是 YES，否则为 NO。
以下是实现上述想法的步骤：
- 如果 n 是奇数，则打印“YES”并返回。
- 如果 n 是偶数，则开始从索引 2 迭代到 n-1，并尝试使所有元素等于前一个元素。
- 但是我们无法对最后一个索引执行操作。
- 如果在从索引 2 迭代到 n-1 之后，如果 arr[n-1] ≤ arr[n]，则打印答案“YES”，否则打印“NO”。
下面是上述方法的实现：
C++
// C++ code for the above approach:
#include
using namespace std;
// Function to check can we sort the
// given operation using these two
// types of operation any numbers of time
bool makesorted(int* arr, int n)
{
// If n is odd,
if (n % 2 != 0) {
return true;
}
// Iterating from index 1 to n-2
for (int i = 1; i <= i - 2; i++) {
// diff = difference between
// arr[i-1] and arr[i]
int diff = arr[i - 1] - arr[i];
// Adding diff to arr[i]
// and arr[i+1]
arr[i] += diff;
// Making all elements equal
// to first element
arr[i + 1] += diff;
}
if (arr[n - 2] <= arr[n - 1]) {
return true;
}
else {
return false;
}
}
// Driver code
int main()
{
int arr[] = { 3, 1, 5, 4 };
int n = sizeof(arr) / sizeof(int);
// Function call
if (makesorted(arr, n)) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
return 0;
}
Java
CODEBLOCK_08c8134a
Python3