自动搬运

查看原文

来自洛谷，原作者为

	2011hym 暴力占据大脑，打表代替思考 | 寒鸦栖枯地，拿分靠暴力 | 空山不见人，爆0就红温

搬运于2025-08-24 22:13:43，当前版本为作者最后更新于2025-05-10 09:16:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

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

题意简述

给定一个长度为 $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$，在最后输出时减一千就可以了。