一维数组的应用¶

最值问题，打擂台¶

前面已经用过打擂台。现在把输入的数据存进数组，再求最大值和最小值。

这里 1 <= n <= 100。

#include <iostream>

using namespace std;

int a[110];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) cin >> a[i];

    long long maxn = -1e18, minn = 1e18;
    for (int i = 0; i < n; i++) {
        if (a[i] > maxn) maxn = a[i];
        if (a[i] < minn) minn = a[i];
    }

    cout << maxn << ' ' << minn;

    return 0;
}

maxn 用极小值初始化，minn 用极大值初始化。 从 a[0] 开始，逐个比较。

这里的初值能覆盖 int 的取值范围。别把 maxn 设成 0，全是负数时会算错。

如果只求最值，后面不用这些数据，也可以边读边比较，不必存数组。

标记数组，桶思想¶

标记数组，记录一个数是否出现过、一个位置是否访问过。

bool vis[5010]; // 全局数组，默认都是false

整数去重

输入 n 个数，每个数在 0~5000 之间，只在第一次出现时输出。

int n, x;
cin >> n;

while (n--) {
    cin >> x;

    if (!vis[x]) {
        cout << x << ' ';
        vis[x] = true;
    }
}

vis[x] 记录的是“数值 x 出现过没有”，不是“第 x 个输入是否出现过”。

5 个数是 3 1 3 2 1，依次输出 3 1 2，保留第一次出现的顺序。

数组开多大，看值域。 值域，就是这些数可能取到的范围。

即使只输入 5 个数，只要可能出现 5000，就要能访问 vis[5000]。负数不能直接当这里的下标。

计数数组，桶思想¶

标记数组，只记“有没有”；计数数组，记录“有几次”。

统计 0 到 9，每个数字出现几次

int cnt[10]; // 全局数组，cnt[x]表示数字x出现了几次

int n, x;
cin >> n;

while (n--) {
    cin >> x; // 保证0 <= x <= 9
    cnt[x]++;
}

for (int i = 0; i < 10; i++) cout << cnt[i] << ' ';

同一个值再次出现，就往同一个“桶”里加一次。

储蓄罐，按编号累加

有 n 个储蓄罐，编号 0~n-1。第 i 天选一个储蓄罐 x，存入 i 元，m 天后输出各罐的钱数。

下面 1 <= n <= 1000、0 <= m <= 100000，输入的 x 是合法编号。

long long box[1010]; // 全局数组，box[x]表示第x个罐有多少钱

int n, m, x;
cin >> n >> m;

for (int i = 1; i <= m; i++) {
    cin >> x;
    box[x] += i;
}

for (int i = 0; i < n; i++) cout << box[i] << ' ';

这里加的是金额 i，不是简单地 box[x]++。

筛选元素存储¶

输入 n 个数，把奇数按原顺序存进新数组，再输出。这里 0 <= n <= 100。

int a[110];

int n, x, idx = 0;
cin >> n;

for (int i = 0; i < n; i++) {
    cin >> x;

    if (x % 2 != 0) a[idx++] = x;
}

for (int i = 0; i < idx; i++) cout << a[i] << ' ';

idx 既是下一个存储位置，也是已经存下来的元素个数。

这两行熟悉以后，可以简写成 a[idx++] = x;。

短除法转进制¶

十进制转二进制，反复除以 2，把余数存进数组。

先得到的是低位，所以最后要倒着输出。下面处理 0 <= n <= 10^9。

int a[110];

int n, idx = 0;
cin >> n;

do {
    a[idx++] = n % 2;
    n /= 2;
} while (n);

for (int i = idx - 1; i >= 0; i--) cout << a[i];

这里用 do while，0 也会存下一位。 输入 0，输出 0，不会什么也不输出。

存储月份¶

月份大小的口诀是：“一三五七八十腊，三十一天永不差；四六九冬三十日，唯有二月二十八”。

如果每次都写一长串 if，很烦。可以把天数提前存起来，月份与下标对应。

int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

这里 mon[0] 不用，mon[1] 对应一月，以此类推。

int y, m;
cin >> y >> m; // 输入正整数年份，月份1~12

if ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0) mon[2] = 29;

cout << mon[m];

这张表按平年存，闰年再把二月改成 29 天。这里每次运行只处理一个年份。

十六进制字符表（先不看）

学过字符串后，再看数字和字符的对应关系。使用 string，需要头文件 <string>。

string s = "0123456789ABCDEF";

cout << s[10]; // 输出A

数组上的移动¶

数组可以表示河中按顺序排列的石头，模拟青蛙往前跳。

n 个石头的位置已经从小到大排好，岸边位置是 0，青蛙每次最多跳 k，问最远能到第几个石头。

这里 0 <= n <= 100，石头位置是递增的正整数，位置和 k 都不超过 10^9，且 k >= 0。

#include <iostream>

using namespace std;

int stone[110];

int main() {
    int n, k;
    cin >> n >> k;

    stone[0] = 0; // 岸边
    for (int i = 1; i <= n; i++) cin >> stone[i];

    int pos = 0;
    for (int i = 1; i <= n; i++) {
        if (stone[i] - stone[i - 1] > k) break;
        pos = i;
    }

    cout << pos;

    return 0;
}

相邻两块石头都跳不过，更远的也跳不过。第一块就到不了，输出 0；全部能到，输出 n。

常见错误¶

把输入顺序，当成数值下标。 标记、计数时，先看清数组的下标代表什么。

处理下一组数据，忘了清空。 同一个标记、计数数组重复使用，要先清除上一组数据的状态。