#P3380. 第2题-数组的区间长度
-
1000ms
Tried: 15
Accepted: 8
Difficulty: 5
所属公司 :
科大讯飞
时间 :2025年8月16日
-
算法标签>思维
第2题-数组的区间长度
题面描述
- 给定一个非降数组 a=a1,a2,…,an(满足 a1≤a2≤⋯≤an)。
- 允许至多一次操作:选择区间 [l,r](1≤l≤r≤n),对任意 i∈[l,r],令 ai←ai+(r−i+1)⋅m。
- 目标:使操作后存在某个 j 满足 aj>aj+1。求所需区间长度 r−l+1 的最小值;若不可能则输出 −1。
思路
-
对区间内部相邻对 i,i+1(l≤i<r),操作后有
- ai′−ai+1′=(ai−ai+1)+m。
-
对右边界相邻对 r,r+1(若 r<n),操作后有
- ar′−ar+1=(ar−ar+1)+m。
-
左边界 l−1,l 不可能制造逆序,因为 al 被增加最多,反而更大。
-
因此能否制造逆序完全取决于是否存在某个相邻差满足
- ai+1−ai<m。
-
一旦存在这样的相邻对,取 r=i 且 l=r(区间长度为 1),就在右边界对 (i,i+1) 上得到
- ai′−ai+1=(ai−ai+1)+m>0。
-
反之,如果对所有 i 都有 ai+1−ai≥m,则无论怎样选 [l,r],相邻差至多增加 m,永远不会变正,答案为 −1。
-
结论:若存在 i 使得 ai+1−ai<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 的数组 {a1,a2,...,an} ,且满足 a1≦a2≦an 。
你可以至多进行一次以下操作:
选择一个区间 [l,r](1≦l≦r≦n) ,对区间内每个 i(1≦i≦r) ,将 ai 变成 ai+(r−i+1)×m 。
请问:为了使操作后数组存在 j 使得 aj>aj+1 ,需要选择的区间长度 r−l+1 的最小值是多少?如果无法通过一次操作满足该要求,则输出 −1 。
输入描述
每个测试文件均包含多组测试数据。
第一行输入一个整数 T(1≦T≦104),代表数据组数;
随后对于每组数据,按以下格式输入:
-
第一行输入两个整数 n,m(2≦n≦2×105,1≤m≤109) ;
-
第二行输入 n 个整数 a1,a2,...,an(1≦ai≦109) 。
此外,保证所有测试数据中 ∑n≦2×105 。
输出描述
对于每组测试数据,输出一个整数,表示所求的最小区间长度;如果无法通过一次操作使数组不再保持非严格递增,输出 −1 。
样例1
输入
2
4 2
1 2 3 3
3 1
2 6 8
输出
1
-1
说明
在第一个测试中,可选择区间 [2,2] ,此时 a2←2+(2−2+1)×2=4,数组变为 ,满足非严格递增,区间长度为 1 。