6335: 2019 阅读程序2:选出不冲突的数对

内存限制:256 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:2 通过:2

题目描述



    程序可以视作通过模拟算法选出一系列互不冲突的数对——若数对(x1,y1)和(x2,y2)之间有x1==x2或y1==y2则认为这两个数对存在冲突,现按顺序考虑每 一个数对(xi,yi)(要求满足前提:在已经选用的数对中,与左值xi匹配的右值小于yi,、与右值yi匹配的左值小于xi),若该数对与此前己经选用的数对冲突, 则用当前数对替换所冲突的原数对;若无冲突,则直接选用当前数对。程序中的 a[x]用于记录,在已选用的数对中,与左值x相匹配的右值;b[y]用于记录,在已选用的数对中,与右值y相匹配的左值;n表示数对左值和右值的取值范围为[l,n];最后的ans用于统计剩余多少左值或右值,没有相应数对被我们选中。



蔚蓝的海边,金色的沙滩上有一个边长为NL型围墙

|

|

|

|

————,

陈晫希望破坏这些围墙来看到更多景色,于是他发明了大功率火炮,可以摧毁它所在行和所在列的围墙,当然也可以摧毁其他的火炮。

但是沙滩可能出现沙陷,只有m个点可以用来放置火炮。

因为最近石油涨价,陈晫不希望他的火炮出现损失,请问在不损失火炮的情况下,剩下的最少的围墙数量。








输入样例 复制

6 4
1 4
3 2
5 2
2 4

输出样例 复制

8

分类标签