CFGym 101490J 题解
一、题目链接
http://codeforces.com/gym/101490
二、题面
三、题意
给你n个点,代表学生所在位置,n个点,代表老师所在位置。每个学生分配一个老师。让你找出一个最小的学生到他的老师的距离(曼哈顿距离),使得其他学生到其老师的距离不超过这个距离。
四、思路
一开始看到这个题,第一反应是N很小,可以考虑暴力搞。但是,压根没思路,暴力都不知道怎么暴。有个很朴素的思路,对第一个学生,枚举每一个老师,计算他和老师的距离,然后,对第二个以后的学生,dfs继续这么干。那这样的话,复杂度是O(100^100) >> O(2 ^ 100)。当时,我想到这个想法时,还和旁边的同学开了个玩笑,我说:我昨晚算了一下,从1循环到2^64次方,需要跑几年。假设普通计算机每秒做10E次操作,约等于10^9。2^64≈10^19,10^19/10^9=10^10(秒),一年也才3000W+秒,要跑300+年。
好了,很明显,上面很Naive的想法肯定是不行的。那怎么办呢?其实这题不难往二分图的方向去想。因为比较裸。我后来看到有同学是用二分图匹配A的。我之前也敲过二分图匹配的题,但是,由于图论方面我没有做太多的训练,只会用用大家都会的图论板子而已。所以,虽然能想到二分图,但是,不知道该怎么去用。后来想到一个办法:二分枚举最大的距离,在原图的基础上删除所有距离比枚举值大的边,跑一遍dfs,如果能连通,则说明此枚举值有效。然而,GG……这个想法也不行。比如这个样例:
然后,我又想到另外一个方法:枚举每一个学生,看看所有的学生所能连接的老师有没有n个,有的话,当前二分的枚举值合法。然后,又找到这样的样例:
思路想到此了,既然这样不行,那我就把老师这边也来一次这样的,如果能连接的学生有n个,那么,这确实可以保证每个学生都和至少一个老师、每个老师都和至少一个学生有连接了。
至于存储能连接的老师有没有n个,这样的方法有很多。我使用的是bitset位存储。
五、源代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL, LL> PLL; int n; PLL stu[], tea[]; vector<][]; LL bas(LL x) { ? -x : x; } LL dis(PLL p1, PLL p2) { return bas(p1.first - p2.first) + bas(p1.second - p2.second); } bitset<> match[][]; bool test(LL mid) { ; i < ; ++i)g[][i].clear(), g[][i].clear(); ; i <= n; ++i) { ; j <= n; ++j) { if(dis(stu[i], tea[j]) <= mid) { g[][i].push_back(j); g[][j].push_back(i); } } } bitset<> res[]; res[].reset(), res[].reset(); ; i <= n; ++i)match[][i].reset(), match[][i].reset(); ; k < ; ++k) { ; i <= n; ++i) { , sz = g[k][i].size(); j < sz; ++j) { int adj = g[k][i][j]; match[k][i].set(adj); } res[k] = res[k] | match[k][i]; } } ].count() == n && res[].count() == n; } int main() { #ifndef ONLINE_JUDGE freopen("Jinput.txt", "r", stdin); #endif // ONLINE_JUDGE while(~scanf("%d", &n)) { ; i <= n; ++i)scanf("%lld%lld", &stu[i].first, &stu[i].second); ; i <= n; ++i)scanf("%lld%lld", &tea[i].first, &tea[i].second); LL low = -, high = 1LL << , mid; ) { mid = (high + low) / ; if(test(mid))high = mid; else low = mid; } printf("%lld\n", high); } ; }
经验:由于习惯了int,这次的long long一不小心又用成了%d输入,然后,调试调了几十分钟,真不应该啊。
最新文章
- 编程之美读书笔记之 -寻找出现次数为1的ID的问题
- web前端学习部落22群分享给需要前端练手项目
- leetcode 179. Largest Number 求最大组合数 ---------- java
- 2016CCPC 合肥--最大公约数//每一年通向它的路上,多少人折戟沉沙,多少人功败垂成,有人一战成名,有人从头再来。
- R如何检验类别变量(nominal variable)与其他变量之间的相关性
- NSString字符操作
- Linux中重命名文件
- CodeForces 441 A. Valera and Antique Items
- Acoustic Echo Cancellation (AEC) 回音消除技术探索
- iconfont.cn阿里巴巴矢量图下载字体图标实战
- ReactiveSwift源码解析(八) SignalProducer的代码的基本实现
- 用标准3层神经网络实现MNIST识别
- 用Eclipse中的git提交代码流程
- TLS调试微信
- jvm的垃圾回收和内存
- 英语进阶系列-A03-英语升级练习一
- springmvc+ajax文件上传
- 什么是 maven的uber-jar
- Vue 项目集合
- js-权威指南学习笔记18