CF390A Inna and Alarm Clock 题解
阅读原文时间:2021年12月23日阅读:1

平面内有 \(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));
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章