题目
Description
Alice 上化学课时又分心了, 他首先画了一个
3
行 N 列的表格, 然后把数字 1 到 N 填入表格的第一行, 保证每个数只出现一次, 另外两行他也填入数字 1 到 N, 但不限制每个数字的出现次数. Alice 现在想删除若干列使得每一行排完序后完全一样, 编程计算最少需要删除多少列.
Input
第一行包含一个整数 N(1<=N<=100000), 表示表格的列数.
接下来三行每行包含 N 个整数, 每个数在 1 到 N 之间, 而且第一行的数互不相同.
Output
输出最少需要删除的列数.
题解
水题
每次找第一行中第二行第三行没有的删掉
当枚举一遍没有删除时输出答案
代码
- #include <cstdio>
- using namespace std;
- int n, row1[100010], row2[100010], row3[100010], count2[100010], count3[100010], tmp, ans;
- int main(int argc, char **argv) {
- scanf("%d", &n);
- for (register int i(0); i < n; ++i) {
- scanf("%d", &row1[i]);
- }
- for (register int i(0); i < n; ++i) {
- scanf("%d", &row2[i]), ++count2[row2[i]];
- }
- for (register int i(0); i < n; ++i) {
- scanf("%d", &row3[i]), ++count3[row3[i]];
- }
- register int finish_flag(0);
- while (!finish_flag) {
- finish_flag = 1;
- for (register int i(0); i < n; ++i) {
- if (row1[i] && !(count2[row1[i]] && count3[row1[i]])) {
- finish_flag = 0;
- ++ans;
- row1[i] = 0;
- --count2[row2[i]], --count3[row3[i]];
- }
- }
- }
- printf("%d\n", ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2741171.html