平面内有 \(n\) 个整点 \((x_i,y_i)\)。每次可以去掉一行或一列的点,问最少去几次(按行去点或按列去点二者只能选择一种)。
数据范围:\(1\leqslant n\leqslant 10^5,0\leqslant x_i,y_i\leqslant 100\)。
既然按行去点或按列去点二者不可得兼,那么我们考虑哪一个需要的次数更少。因此,统计横坐标和纵坐标的种数,就可以计算出按行去点和按列去点需要的次数,再在其中取最小值即可。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
int n, x, y, row[107], line[107], ans1, ans2;
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d%d", &x, &y);
if(!row[x]) ans1 += (row[x] = 1);
if(!line[y]) ans2 += (line[y] = 1);
}
printf("%d", min(ans1, ans2));
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章