Cho mảng số nguyên A[] gồm N phần tử, hãy tìm vị trí(bắt đầu từ 0) cuối cùng của…
Input Format
Dòng đầu tiên là N : số lượng phần tử trong mảng; Dòng thứ 2 gồm N phần tử viết cách nhau một khoảng trống.
Constraints
1<=N<=10^6; 1<=A[i]<=10^6
Output Format
In trên 1 dòng 2 chỉ số mà bạn tìm được.
Sample Input 0
9
936 234 471 168 834 82 280 674 881
Sample Output 0
5 0
Phân tích đề bài:
Đề bài yêu cầu chúng ta tìm hai vị trí đặc biệt trong một mảng số nguyên A[] gồm N phần tử:
1. Vị trí cuối cùng của giá trị nhỏ nhất.
2. Vị trí đầu tiên của giá trị lớn nhất.
Điều quan trọng cần lưu ý là:
* Nếu có nhiều phần tử có cùng giá trị nhỏ nhất, ta phải lấy vị trí của phần tử xuất hiện sau cùng.
* Nếu có nhiều phần tử có cùng giá trị lớn nhất, ta phải lấy vị trí của phần tử xuất hiện trước tiên.
* Vị trí của mảng bắt đầu từ 0.
Chiến lược giải:
Để giải quyết bài toán này, chúng ta cần hai bước chính:
Bước 1: Tìm giá trị nhỏ nhất và vị trí cuối cùng của nó.
Bước 2: Tìm giá trị lớn nhất và vị trí đầu tiên của nó.
Chúng ta sẽ đi qua mảng một lần để tìm cả hai thông tin này.
Các biến cần sử dụng:
* \(N\): Số lượng phần tử trong mảng.
* \(A[]\): Mảng chứa các phần tử số nguyên.
* \(min_val\): Biến lưu trữ giá trị nhỏ nhất tìm được.
* \(min_idx\): Biến lưu trữ vị trí cuối cùng của giá trị nhỏ nhất.
* \(max_val\): Biến lưu trữ giá trị lớn nhất tìm được.
* \(max_idx\): Biến lưu trữ vị trí đầu tiên của giá trị lớn nhất.
Thuật toán chi tiết:
1. Khởi tạo:
* Đọc giá trị \(N\).
* Khởi tạo mảng \(A\) có \(N\) phần tử.
* Để tìm giá trị nhỏ nhất và lớn nhất ban đầu, chúng ta có thể lấy phần tử đầu tiên của mảng để khởi tạo.
* \(min_val = A[0]\)
* \(min_idx = 0\)
* \(max_val = A[0]\)
* \(max_idx = 0\)
* Lý do khởi tạo như vậy là để đảm bảo rằng chúng ta có một giá trị tham chiếu ban đầu. Nếu mảng chỉ có 1 phần tử, thì phần tử đó vừa là nhỏ nhất, vừa là lớn nhất, và vị trí cuối cùng/đầu tiên đều là 0.
2. Duyệt mảng để tìm giá trị nhỏ nhất và lớn nhất:
* Chúng ta sẽ duyệt mảng từ phần tử thứ hai (chỉ số 1) cho đến phần tử cuối cùng (chỉ số \(N-1\)).
* Với mỗi phần tử \(A[i]\) đang xét (với \(i\) chạy từ 1 đến \(N-1\)):
* Kiểm tra giá trị nhỏ nhất:
* Nếu \(A[i] < min_val\):
* Điều này có nghĩa là chúng ta vừa tìm thấy một giá trị nhỏ hơn giá trị nhỏ nhất hiện tại.
* Cập nhật \(min_val = A[i]\).
* Cập nhật \(min_idx = i\). (Vì chúng ta muốn vị trí cuối cùng của giá trị nhỏ nhất, mỗi lần tìm thấy một giá trị nhỏ hơn, chúng ta đều cập nhật vị trí mới).
* Nếu \(A[i] == min_val\):
* Điều này có nghĩa là chúng ta tìm thấy một giá trị bằng với giá trị nhỏ nhất hiện tại. Theo yêu cầu đề bài, chúng ta cần vị trí cuối cùng của giá trị nhỏ nhất. Do đó, chúng ta vẫn cần cập nhật vị trí.
* Cập nhật \(min_idx = i\).
* Kiểm tra giá trị lớn nhất:
* Nếu \(A[i] > max_val\):
* Điều này có nghĩa là chúng ta vừa tìm thấy một giá trị lớn hơn giá trị lớn nhất hiện tại.
* Cập nhật \(max_val = A[i]\).
Cập nhật \(max_idx = i\). (Vì chúng ta muốn vị trí đầu tiên* của giá trị lớn nhất, chúng ta chỉ cập nhật \(max_idx\) khi tìm thấy một giá trị lớn hơn hẳn. Nếu gặp giá trị bằng \(max_val\), chúng ta sẽ không cập nhật \(max_idx\) nữa, giữ nguyên vị trí đầu tiên đã tìm được).
* Nếu \(A[i] == max_val\):
Chúng ta không cần làm gì cả. Bởi vì \(max_idx\) đã lưu trữ vị trí đầu tiên* của giá trị lớn nhất. Việc gặp một giá trị bằng \(max_val\) ở các vị trí sau không ảnh hưởng đến yêu cầu tìm vị trí đầu tiên.
3. Kết quả:
* Sau khi duyệt hết mảng, biến \(min_idx\) sẽ lưu vị trí cuối cùng của giá trị nhỏ nhất, và biến \(max_idx\) sẽ lưu vị trí đầu tiên của giá trị lớn nhất.
* In ra \(max_idx\) và \(min_idx\) cách nhau một khoảng trống.
Ví dụ minh họa với Sample Input 0:
Input:
N = 9
A = [936, 234, 471, 168, 834, 82, 280, 674, 881]
Quá trình thực hiện:
* Khởi tạo:
* \(N = 9\)
* \(A = [936, 234, 471, 168, 834, 82, 280, 674, 881]\)
* \(min_val = A[0] = 936\)
* \(min_idx = 0\)
* \(max_val = A[0] = 936\)
* \(max_idx = 0\)
* Duyệt mảng từ i = 1 đến 8:
* i = 1, A[1] = 234
* \(A[1] < min_val\) (234 < 936) => \(min_val = 234\), \(min_idx = 1\)
* \(A[1] < max_val\) (234 < 936) => Không thay đổi \(max_val\), \(max_idx\).
* i = 2, A[2] = 471
* \(A[2] > min_val\) (471 > 234) => Không thay đổi \(min_val\), \(min_idx\).
* \(A[2] < max_val\) (471 < 936) => Không thay đổi \(max_val\), \(max_idx\).
* i = 3, A[3] = 168
* \(A[3] < min_val\) (168 < 234) => \(min_val = 168\), \(min_idx = 3\)
* \(A[3] < max_val\) (168 < 936) => Không thay đổi \(max_val\), \(max_idx\).
* i = 4, A[4] = 834
* \(A[4] > min_val\) (834 > 168) => Không thay đổi \(min_val\), \(min_idx\).
* \(A[4] < max_val\) (834 < 936) => Không thay đổi \(max_val\), \(max_idx\).
* i = 5, A[5] = 82
* \(A[5] < min_val\) (82 < 168) => \(min_val = 82\), \(min_idx = 5\)
* \(A[5] < max_val\) (82 < 936) => Không thay đổi \(max_val\), \(max_idx\).
* i = 6, A[6] = 280
* \(A[6] > min_val\) (280 > 82) => Không thay đổi \(min_val\), \(min_idx\).
* \(A[6] < max_val\) (280 < 936) => Không thay đổi \(max_val\), \(max_idx\).
* i = 7, A[7] = 674
* \(A[7] > min_val\) (674 > 82) => Không thay đổi \(min_val\), \(min_idx\).
* \(A[7] < max_val\) (674 < 936) => Không thay đổi \(max_val\), \(max_idx\).
* i = 8, A[8] = 881
* \(A[8] > min_val\) (881 > 82) => Không thay đổi \(min_val\), \(min_idx\).
* \(A[8] < max_val\) (881 < 936) => Không thay đổi \(max_val\), \(max_idx\).
* Kết thúc vòng lặp.
* Kiểm tra lại với giá trị lớn nhất:
* Ồ, cô quên một bước nhỏ trong quá trình duyệt. Khi gặp \(A[0] = 936\), \(max_val\) được khởi tạo là 936 và \(max_idx\) là 0.
* Chúng ta cần kiểm tra lại xem có phần tử nào lớn hơn 936 không.
* À, trong ví dụ này, giá trị lớn nhất thực sự là 936 và nó xuất hiện ở vị trí đầu tiên (chỉ số 0).
* Nếu mảng có giá trị lớn hơn 936, ví dụ: \([936, 234, 471, 168, 834, 82, 280, 674, 900, 950]\)
* Lúc đó, khi duyệt đến 950 (chỉ số 9), ta sẽ có:
* \(A[9] > max_val\) (950 > 936) => \(max_val = 950\), \(max_idx = 9\).
* Trong sample input 0, giá trị lớn nhất là 936 và nó xuất hiện duy nhất ở vị trí 0. Do đó, \(max_idx\) vẫn là 0.
* Kết quả cuối cùng:
* \(min_idx = 5\) (vị trí cuối cùng của giá trị nhỏ nhất 82)
* \(max_idx = 0\) (vị trí đầu tiên của giá trị lớn nhất 936)
* In ra: 0 5 (Oops, sample output là 5 0. Đề bài yêu cầu in ra “vị trí cuối cùng của giá trị nhỏ nhất” TRƯỚC, rồi mới đến “vị trí đầu tiên của giá trị lớn nhất”. Vậy thứ tự in sẽ là min_idx rồi mới đến max_idx. Tuy nhiên, Sample Output 0 lại in 5 0, tức là \(min_idx\) rồi \(max_idx\). Cô xin lỗi vì sự nhầm lẫn này, ta sẽ in theo thứ tự của sample output).
* Đúng rồi, Sample Output 0 là 5 0. Vậy là chúng ta in vị trí nhỏ nhất trước, rồi đến vị trí lớn nhất.
* => In ra: 5 0.
Mở rộng và lưu ý:
* Độ phức tạp thuật toán:
* Chúng ta chỉ duyệt qua mảng một lần duy nhất. Do đó, độ phức tạp về thời gian là O(N).
* Chúng ta chỉ sử dụng một vài biến phụ để lưu trữ, nên độ phức tạp về không gian là O(1) (không phụ thuộc vào kích thước của mảng). Đây là một thuật toán rất hiệu quả.
* Kiểm tra giới hạn:
* N có thể lên tới 10^6, A[i] cũng lên tới 10^6. Các kiểu dữ liệu cơ bản (như \(int\) trong C++ hoặc \(int\) trong Python) đều đủ sức chứa các giá trị này.
Cấu trúc mã giả (Python):
python
# Đọc N
N = int(input())
# Đọc mảng A
A = list(map(int, input().split()))
# Khởi tạo
min_val = A[0]
min_idx = 0
max_val = A[0]
max_idx = 0
# Duyệt mảng từ phần tử thứ 2
for i in range(1, N):
# Tìm vị trí cuối cùng của giá trị nhỏ nhất
if A[i] <= min_val: # Dùng <= để đảm bảo lấy vị trí cuối cùng nếu có nhiều số bằng nhau
min_val = A[i]
min_idx = i
# Tìm vị trí đầu tiên của giá trị lớn nhất
if A[i] > max_val: # Chỉ cập nhật khi tìm thấy giá trị lớn hơn hẳn
max_val = A[i]
max_idx = i
# In kết quả theo thứ tự của Sample Output
print(min_idx, max_idx)
Các em thấy đó, với một bài toán tưởng chừng phức tạp nhưng khi chúng ta phân tích kỹ từng yêu cầu, chia nhỏ vấn đề và xây dựng thuật toán logic, chúng ta hoàn toàn có thể giải quyết nó một cách hiệu quả.
Chúc các em học tốt! Có em nào có câu hỏi không?
#include <bits/stdc++.h>
using namespace std;
int n, a[1000005], temp = 0;
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
if (a[i] > temp)
temp = a[i];
}
int minn = 1e7, v1 = -1, v2 = -1;
for (int i = 0; i < n; i++)
{
if (a[i] < minn)
{
minn = a[i];
v1 = i;
}
if (v2 == -1)
{
if (a[i] == temp)
{
v2 = i;
}
}
}
cout << v1 << ” ” << v2;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int min=a[0],max=a[0],min_a=0,max_a=0;
for(int i=0;i<n;i++){
if(a[i]<=min){
min =a[i];
min_a=i;}
if(a[i]>max){
max =a[i];
max_a=[i];}}
cout<<min_a<<” “<<max_a<<endl;
return 0;}