一维¶
最值问题，打擂台¶
求最大值、最小值，采用 "打擂台" 的方式进行。
int a[110], n, maxn = -1, minn = 2e9;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
maxn = max(maxn, a[i]);
minn = min(minn, a[i]);
}
cout << maxn << ' ' << minn;
return 0;
}
标记数组，桶思想¶
标记数组，用于维护元素的状态（是否出现过、是否访问过、是否处理过）。
整数去重
例题，输入n个数，每个数字只在它第一次出现的时候输出
bool vis[5010]; // vis[i]表示 i 这个数值是否出现过，vis数组的大小取决于值域
int n, x;
int main() {
cin >> n;
while (n--){
cin >> x;
if (!vis[x]){
cout << x << ' ';
vis[x] = true;
}
}
return 0;
}
计数数组，桶思想¶
计数数组，用于统计元素出现的次数，统计这个编号的位置存了多少东西。
例题，有 n 个数，值域范围是 0 - 9，输出 0 - 9 这 10 个数字，每个数字出现多少次
int cnt[15], n, x;
int main() {
cin >> n;
while (n--) {
cin >> x;
cnt[x]++;
}
for (int i = 0; i < 10; i++) cout << cnt[i] << ' ';
return 0;
}
例题，有 n 个储蓄罐，编号 0 ~ n-1，第 i 天挑选一个储蓄罐 x，存入 i 元
m 天后，输出每个储蓄罐里的钱数
int cnt[1010], n, m, x; // cnt[i] 表示第 i 个储蓄罐有多少钱
int main() {
cin >> n >> m;
for (int i = 1; i <= m, i++) {
cin >> x;
cnt[x] += i;
}
for (int i = 0; i < n; i++) cout << cnt[i] << ' ';
return 0;
}
筛选元素存储¶
输入 n 个数，并非把 n 个数都存起来，而是把满足条件的数存起来。
具体有多少个数要存？要看实际有多少个满足条件的数。
例题，输入 n 个数，将其中的奇数存起来，放到一个新的数组里，并依次输出
int a[110], n, idx, x;
int main() {
cin >> n;
while (n--) {
cin >> x;
if (x % 2) a[idx++] = x;
}
for (int i = 0; i < idx; i++) cout << a[i] << ' ';
return 0;
}
短除法转进制
例题，输入一个十进制数 n，转成二进制（将余数存到数组中）
int a[110], n, idx;
int main() {
cin >> n;
while (n) {
a[idx++] = n % 2;
n /= 2;
}
for (int i = idx - 1; i >= 0; i--) cout << a[i]; // 从后向前输出
return 0;
}
存储月份¶
月份大小的口诀是：“一三五七八十腊，三十一天永不差；四六九冬三十日，唯有二月二十八”。
但在写程序时，要写很多个 if，那是很烦的。
我们可以用数组将每个月份对应的天数存起来，和下标对应上，这样就可以通过下标访问，快速得到月份天数。
// 如果不用数组预先存储起来，就需要用if进行判断
if (m == 1 || m == 3 || m == 5 || m == 7 || m == 8 || m == 10 || m == 12) cout << 31;
else if (m == 4 || m == 6 || m == 9 || m == 11) cout << 31;
else cout << 28;
相同的，我们在进行十进制转十六进制的时候，会遇到 ABCDEF 的情况，那要写很多 if 语句，很是麻烦。
于是，我们可以把数字和字符的转化关系，存到一个数组里，方便使用。
我们到目前为止，还没有学习到 string 是什么。
不妨往前翻一翻，看一下 string 的基本定义，就能理解这里了。
数组上的移动¶
我们可以用数组表示过河时，河中间的一排石头，模拟跳石头过河的过程。
这个过程，就是数组上的移动、跳跃、按一定规则选择元素的过程。
例题，河中有 n 个石头，排成一列指向对岸，小青蛙最长跳跃距离是 k
问，小青蛙最多可以跳到第几个石头上