打标记

例如有编号1-n的n个白色盘子,炼石熊准备在一些盘子上

涂颜色,可能会重复选择某一些盘子涂颜色,问最后哪些

盘子还是白色,按编号从小到大输出。

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int arr[N];
int main() {
	int n,m,x;
	cin >> n >> m;
	for (int i = 1;i <= m; i++) {
		int num;
		cin >> num;
		arr[num] = 1;
	}
	for (int i = 1;i <= n; i++) {
		if (arr[i] == 0) {
			cout << i << " ";
		}
	}
	return 0;
}
解析 对于这一类问题,我们可以用数组下标对应盘子的编号,数组

元素的值表示颜色状态。 对于上述问题用数组bi表示编号为i盘子的涂色状 态,b[i]=1(bl类型),表示涂了颜色(bool值为true),b[i]=0表 示没有涂过颜色(boo值为 false),重复涂色的盘子最终状态 依然为1。这样,问题就变成了涂色的盘子标记为1,没有涂 过色的盘子标记为0。 盘子编号分别为1 2 3 4 5 6。数据中画线部分表示1~n中 被涂了颜色的盘子,最后循环判断,如果 b[i]为0,输出i。