2209H 零食售卖点

览遍千秋 · 2022-09-15 00:03:27 · 题解

Source & Knowledge

2022 年 9 月语言月赛，由洛谷网校入门计划/基础计划提供。

由 expect2004 命题。

考察简单排序。

注意到要求两个相邻的零食售卖点，a_i 又不是升序给出，考虑对 a_i 排序。

可以使用 sort 库函数。

sort(a + 1, a + n + 1);

默认升序排序。

对于本题所给数据范围，时间复杂度 \mathcal O(n^2) 的冒泡排序也可以通过。

for(int i = 1; i <= n; i++)
    for(int j = 1; j < i; j++)
        if(a[i] > a[j]) swap(a[i], a[j]);

注意到本题值域较小，仅有 10^7，计数排序也可以通过本题。