题解：P5718 【深基4.例2】找最小值

· · 题解

前言

大佬已经讲过打擂台的做法了，我就讲一下别的。

题意简述

给定一个长度为 n 的序列，求序列中的最小值。

解题思路

这道题可以作为排序算法的入门题，以下内容是对排序的讲解：

STL 排序

排序算法，OI Wiki 上这样说：

排序算法（英语：Sorting algorithm）是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样，性质也大多不同。

确实，排序分为很多种算法，在此题中我们选择 STL 中的排序算法，如下：

//a[1] .. a[n] 为需要排序的数列。
//对 a 原地排序，将其按从小到大的顺序排列。
sort(a+1,a+1+n);

这种排序作为赛场上最常用的排序算法之一，可以将一个序列从小到大排序，时间复杂度为 O(n\log n)。

对于此题而言，我们就可以排序之后输出数组的第一个元素，即序列中最小值。

#include<bits/stdc++.h>//万能头。
using namespace std;
int n,a[110];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);//排序。
    cout<<a[1];//输出最小值。
    return 0;
}

桶排序改装版

这种算法适用于数组中的数值域较小（在 10^8 之内）寻找最小值、最大值和某数出现次数。

它的实现就是用一个数组存储所有数出现的次数。

假设出现了一个数 x，则对应 x 的数组就加一。

这种方法可以在两次循环内完成，时间复杂度较优。

#include<bits/stdc++.h>//万能头。
using namespace std;
int n,a[110],tong[1010];//tong 的大小就是 a 数组的值域。
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        tong[a[i]]++;
    }
    for(int i=0;i<=1000;i++){//a 的值域。
        if(tong[i]!=0){//找到第一个出现的数。
            cout<<i;
            return 0;
        }
    }
}

这里有个问题：如果这个数的值可能为负数，那数组开不了负数怎么办？

假设值域范围是 -1000\le a_i\le 1000，那么我们就可以整体加上一千，使其变成 0\le a_i\le 2000，在最后输出时减一千就可以了。