Editorial for minmax: Số bé nhất và số lớn nhất

Hiểu bài toán

Bài toán yêu cầu tìm phần tử nhỏ nhất (minimum) và phần tử lớn nhất (maximum) trong một dãy số nguyên gồm n phần tử. Ngoài ra, cần in ra vị trí (tính từ 1) của phần tử nhỏ nhất đầu tiên và phần tử lớn nhất đầu tiên xuất hiện trong dãy. Nếu có nhiều phần tử bằng nhau cùng có giá trị nhỏ nhất (hoặc lớn nhất), ta phải chọn phần tử xuất hiện đầu tiên.

Các cách tiếp cận

Cách Duyệt đơn giản (Single Pass)

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#include<math.h>
int main(){
    int n;
    scanf("%d",&n);
    long long a[n];
    for(int i=0;i<n;i++) scanf("%lld",&a[i]);
    long long max=-1e6-1;
    long long min=1e6+1;
    int minpos,maxpos;
    for(int i=0;i<n;i++){
        if(a[i]>max){
            max=a[i];
            maxpos=i;
        }
        if(a[i]<min){
            min=a[i];
            minpos=i;
        }
    }
    printf("%lld %d %lld %d",min,minpos+1,max,maxpos+1);
}

• Time Complexity: O(n)
• Space Complexity: O(n) (hoặc O(1) nếu chỉ lưu giá trị)

Đây là cách tiếp cận hiệu quả nhất. Ta duyệt qua mảng một lần duy nhất, vừa duyệt vừa cập nhật giá trị nhỏ nhất và lớn nhất cùng chỉ số của chúng. Điều kiện a[i] < min (hoặc a[i] > max) đảm bảo rằng nếu gặp giá trị bằng với giá trị hiện tại, chỉ số sẽ không được cập nhật, từ đó chọn được phần tử xuất hiện đầu tiên. Cần lưu ý khởi tạo giá trị max/min đủ lớn để xử lý các số âm/duyệt qua tất cả phần tử.

Cách Sử dụng hàm qsort

#include <stdio.h>
#include <stdlib.h>

#define MAX 100005

typedef struct{
    long long val;
    int pos;
} ele;
long long a[MAX];
ele tmp[MAX];

int compareval(const void *a, const void *b) {
    const ele *e1 = (const ele*)a;
    const ele *e2 = (const ele*)b;

    if (e1->val < e2->val) return -1;
    if (e1->val > e2->val) return 1;
    return e1->pos - e2->pos;
}

int main() {
    int n;
    scanf("%d",&n);
    for (int i = 0;i < n;i++){
        scanf("%lld",&a[i]);
        tmp[i].val = a[i];
        tmp[i].pos = i;
    }
    qsort(tmp,n,sizeof(ele),compareval);
    int x = 0;
    tmp[x] = tmp[0];
    for (int i = 1;i < n;i++){
        if (tmp[i].val != tmp[x].val){
            x+=1;
            tmp[x] = tmp[i];
        }
    }
     printf("%lld %d %lld %d",tmp[0].val,tmp[0].pos+1,tmp[x].val,tmp[x].pos+1);
    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Phương pháp này tạo một mảng cấu trúc chứa giá trị và chỉ số ban đầu. Sau đó sắp xếp mảng này theo giá trị tăng dần. Hàm so sánh compareval ưu tiên giá trị nhỏ hơn, nếu bằng nhau thì so sánh chỉ số (chỉ số nhỏ hơn sẽ đứng trước). Phần tử đầu tiên của mảng sau khi sắp xếp là đáp án cho số bé nhất. Để tìm số lớn nhất đầu tiên, ta cần duyệt từ cuối mảng về hoặc loại bỏ các phần tử trùng lặp giá trị (deduplicate) và lấy phần tử cuối cùng của mảng đã loại bỏ trùng lặp. Phương pháp này chậm hơn do chi phí sắp xếp.

Cách Duyệt 2 vòng lặp riêng biệt

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define ll long long
#define sc scanf
#define pr printf

int main() {
    int n; sc("%d",&n);
    int a[n+1];
    for(int i=1; i<=n; i++) sc("%d",&a[i]);
    int min=a[1], max=a[1];
    int vitrimax=1, vitrimin=1;
    for(int i=2; i<=n; i++){
        if(a[i] < min){
            min = a[i];
            vitrimin = i;
        }
    }
    for(int j=2; j<=n; j++){
        if(a[j] > max){
            max = a[j];
            vitrimax = j;
        }
    }
    pr("%d %d %d %d\n",min,vitrimin,max,vitrimax);
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Cách này chia bài toán làm 2 phần: tìm min và tìm max. Mỗi phần duyệt một vòng lặp riêng. Về độ phức tạp thời gian vẫn là O(n) vì 2*O(n) = O(n). Tuy nhiên, cách này đi ngược lại quy ước 'Single Pass' (duyệt 1 lần) và nếu dữ liệu nhập vào là stream (luồng) thì không thể thực hiện được do không lưu trữ được hết bộ nhớ. Tuy nhiên với约束 (constraints) của bài này thì cách này hoàn toàn hợp lệ.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Để đảm bảo chọn được phần tử xuất hiện đầu tiên khi có nhiều giá trị bằng nhau, điều kiện cập nhật phải là 'nghiệm ngặt' (strict): < cho min và > cho max.
• Vị trí trong output yêu cầu tính từ 1, trong khi chỉ số mảng trong C/C++ tính từ 0, do đó cần cộng thêm 1 khi in kết quả.

Lỗi thường gặp

• Khởi tạo sai giá trị ban đầu cho min/max. Ví dụ: khởi tạo min = 0 nhưng dãy số có thể toàn số âm. Nên dùng giá trị của phần tử đầu tiên làm giá trị ban đầu hoặc dùng giá trị tối thiểu/tối đa của kiểu dữ liệu.
• Quên xử lý trường hợp n = 1 (dãy chỉ có 1 phần tử) hoặc nhập xuất sai định dạng (dùng %d cho long long).