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

Xem PDF
Tác giả:
jumptozero
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


  • 0
    thuannguyen1972dn    5:57 p.m. 2 Tháng 5, 2024

    python:làm mún ẻ chải:
    def find_maximum_difference(arr):
    n = len(arr)
    max_diff = float('-inf') # Giá trị khác nhau lớn nhất
    min_value = arr[0] # Giá trị nhỏ nhất mà chúng tôi đã thấy

    best_i = 0
best_j = 0

# Duyệt qua từng phần tử từ thứ 2 đến cuối mảng
for j in range(1, n):
    # Tính sự khác nhau a[j] - a[i] với i < j
    current_diff = arr[j] - min_value

    # Kiểm tra nếu sự khác nhau hiện tại lớn hơn sự khác nhau lớn nhất đã biết
    if current_diff > max_diff:
        max_diff = current_diff
        best_i = arr.index(min_value) + 1  # Tìm chỉ số i tương ứng với giá trị nhỏ nhất
        best_j = j + 1  # Chỉ số j (từ 1-indexed)

    # Cập nhật giá trị nhỏ nhất đã thấy
    if arr[j] < min_value:
        min_value = arr[j]

return (best_i, best_j)

    Đọc input

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

    Tìm chỉ số i và j thỏa mãn điều kiện a[j] - a[i] là lớn nhất

    best_i, best_j = find_maximum_difference(arr)
    print(best_i, best_j)
    print(arr[best_j-1] - arr[best_i-1])

    • 11 bình luận nữa