Hai phần tử dễ thương

Tác giả:

Dạng bài

Điểm: 300 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một mảng gồm \(n\) số nguyên . Tìm \(2\) chỉ số \(i,j\) thỏa mãn \(1\le i<j\le n\) và \(a[j]-a[i]\) đạt giá trị lớn nhất.

Input

Dòng thứ nhất chứa số nguyên dương \(n(2\le n\le 10^5)\)
Dòng thứ hai chứa \(n\) số nguyên \(a_i(-10^3\le a_i\le 10^3 \text{ }\forall 1\le i\le n)\)

Output

Dòng thứ nhất chứa hai chỉ số \(i,j\) thỏa mãn yêu cầu bài toán
Dòng thứ hai in ra giá trị \(a[j]-a[i]\)

(Chú ý nếu có nhiều đáp án in ra đáp án bất kì).

Example

Test 1

Input

3
1 2 3

Output

1 3
2

Bình luận

python không vòng lặp:

n = int(input())
m = list(map(int, input().split()))

a1 = m.index(min(m[:-1]))  # tìm i nhỏ nhất trước
b1 = m[a1 + 1:].index(max(m[a1 + 1:])) + a1 + 1  # tìm j lớn nhất sau

w1 = m[b1] - m[a1]  # đáp án trường hợp 1

m.reverse()  # tìm chiều ngược lại
b2 = m.index(max(m[:-1]))  # tìm j lớn nhất trước
a2 = m[b2 + 1:].index(min(m[b2 + 1:])) + b2 + 1  # tìm i nhỏ nhất sau
m.reverse()  # trả mảng như cũ

# vì tìm trong mảng bị đổi chiều nên sửa lại
a2 = n - a2
b2 = n - b2

w2 = m[b2] - m[a2]  # đáp án trường hợp 2

if w1 <= w2:
    print(a2 + 1, b2 + 1)  # nếu trường hợp 2 là max
else:
    print(a1 + 1, b1 + 1)
print(max(w1, w2))

15 bình luận nữa