题面描述

• 给定一个非降数组 $a={a_1,a_2,\ldots,a_n}$（满足 $a_1\le a_2\le\cdots\le a_n$）。
• 允许至多一次操作：选择区间 $[l,r]$（$1\le l\le r\le n$），对任意 $i\in[l,r]$，令 $a_i\leftarrow a_i+(r-i+1)\cdot m$。
• 目标：使操作后存在某个 $j$ 满足 $a_j>a_{j+1}$。求所需区间长度 $r-l+1$ 的最小值；若不可能则输出 $-1$。

思路

• 对区间内部相邻对 $i,i+1$（$l\le i<r$），操作后有

  • $a_i'-a_{i+1}'=(a_i-a_{i+1})+m$。

• 对右边界相邻对 $r,r+1$（若 $r<n$），操作后有

  • $a_r'-a_{r+1}=(a_r-a_{r+1})+m$。

• 左边界 $l-1,l$ 不可能制造逆序，因为 $a_l$ 被增加最多，反而更大。

• 因此能否制造逆序完全取决于是否存在某个相邻差满足

  • $a_{i+1}-a_i<m$。

• 一旦存在这样的相邻对，取 $r=i$ 且 $l=r$（区间长度为 $1$），就在右边界对 $(i,i+1)$ 上得到

  • $a_i'-a_{i+1}=(a_i-a_{i+1})+m>0$。

• 反之，如果对所有 $i$ 都有 $a_{i+1}-a_i\ge m$，则无论怎样选 $[l,r]$，相邻差至多增加 $m$，永远不会变正，答案为 $-1$。

• 结论：若存在 $i$ 使得 $a_{i+1}-a_i<m$，答案为 $1$；否则为 $-1$。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	if (!(cin >> T)) return 0;
	while (T--) {
		int n;
		long long m;
		cin >> n >> m;
		vector<long long> a(n);
		for (int i = 0; i < n; ++i) cin >> a[i];

		// 只需检查是否存在相邻差小于 m
		bool ok = false;
		for (int i = 0; i + 1 < n; ++i) {
			if (a[i + 1] - a[i] < m) {
				ok = true;
				break;
			}
		}
		cout << (ok ? 1 : -1) << "\n";
	}
	return 0;
}

Python

import sys

def solve():
	data = list(map(int, sys.stdin.read().strip().split()))
	it = iter(data)
	T = next(it, 0)
	out = []
	for _ in range(T):
		n = next(it); m = next(it)
		a = [next(it) for _ in range(n)]
		# 只需检查是否存在相邻差小于 m
		ans = -1
		for i in range(n - 1):
			if a[i + 1] - a[i] < m:
				ans = 1
				break
		out.append(str(ans))
	print("\n".join(out))

if __name__ == "__main__":
	solve()

Java

import java.io.*;
import java.util.*;

public class Main {
	static class FastScanner {
		private final InputStream in;
		private final byte[] buffer = new byte[1 << 16];
		private int ptr = 0, len = 0;
		FastScanner(InputStream is) { in = is; }
		private int read() throws IOException {
			if (ptr >= len) {
				len = in.read(buffer);
				ptr = 0;
				if (len <= 0) return -1;
			}
			return buffer[ptr++];
		}
		int nextInt() throws IOException {
			int c, sgn = 1, x = 0;
			do { c = read(); } while (c <= ' ' && c != -1);
			if (c == '-') { sgn = -1; c = read(); }
			while (c > ' ') {
				x = x * 10 + (c - '0');
				c = read();
			}
			return x * sgn;
		}
		long nextLong() throws IOException {
			int c, sgn = 1;
			long x = 0;
			do { c = read(); } while (c <= ' ' && c != -1);
			if (c == '-') { sgn = -1; c = read(); }
			while (c > ' ') {
				x = x * 10 + (c - '0');
				c = read();
			}
			return x * sgn;
		}
	}

	public static void main(String[] args) throws Exception {
		FastScanner fs = new FastScanner(System.in);
		StringBuilder sb = new StringBuilder();
		int T = fs.nextInt();
		while (T-- > 0) {
			int n = fs.nextInt();
			long m = fs.nextLong();
			long[] a = new long[n];
			for (int i = 0; i < n; i++) a[i] = fs.nextLong();

			// 只需检查是否存在相邻差小于 m
			int ans = -1;
			for (int i = 0; i + 1 < n; i++) {
				if (a[i + 1] - a[i] < m) {
					ans = 1;
					break;
				}
			}
			sb.append(ans).append('\n');
		}
		System.out.print(sb.toString());
	}
}

题目内容

给定一个长度为 $n$ 的数组 {$a_1,a_2,...,a_n$} ，且满足 $a_1≦a_2≦a_n$ 。

你可以至多进行一次以下操作：

选择一个区间 $[l,r] (1 ≦l≦r≦n)$ ，对区间内每个 $i(1≦i≦r)$ ,将 $a_i$ 变成 $a_i+(r-i+1)×m$ 。

请问：为了使操作后数组存在 $j$ 使得 $a_j>a_{j+1}$ ，需要选择的区间长度 $r-l+1$ 的最小值是多少?如果无法通过一次操作满足该要求，则输出 $-1$ 。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数 $T(1≦T≦10^4)$，代表数据组数；

随后对于每组数据，按以下格式输入：

• 第一行输入两个整数 $n,m(2≦n≦2×10^5,1≤m≤10^9)$ ；

• 第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≦a_i≦10^9)$ 。

此外，保证所有测试数据中 $\sum n≦2×10^5$ 。

输出描述

对于每组测试数据，输出一个整数，表示所求的最小区间长度；如果无法通过一次操作使数组不再保持非严格递增，输出 $-1$ 。

样例1

输入

2
4 2
1 2 3 3
3 1
2 6 8

输出

1
-1

说明

在第一个测试中，可选择区间 $[2,2]$ ，此时 $a_2←2+(2-2+1)×2=4$，数组变为 ，满足非严格递增，区间长度为 $1$ 。