在地图上散落着 n 个车轮,小 J 想用它们造一辆车。要求如下:
1. 一辆车需要四个车轮,且四个车轮构成一个正方形
2. 车轮不能移动你需要计算有多少种造车的方案(两个方案不同当且仅当所用车轮不全相同,坐标相同的两个车轮视为不同车轮)。
30%的数据保证 n ≤ 30
100%的数据保证 1 ≤ n ≤ 1000; |x|, |y| < 20000
其实和这个题一样的思路。就不赘述了。
然而为什么要发这篇题解,因为这个题地图范围更大,二维数组存不下,于是我又双叒被map教做人了!!(本周第三次)
所以这篇题解仅仅小小讨论一下STL这群坑比
我去访问有没有这个点对,以及出现了多少次的时候 我是这样写的
我自己用clock测出来跑了4000多ms,我坚信这不科学啊,我写的一定是正解,肯定是机子太老年了,于是写完题玩了一个多小时。。
然后就真的挂了。。
后来调用机房几个dalao也没瞅出来问题在哪,在我的一番试验和推测过后,终于找到了!!
大概是我访问了不存在的元素!!因为map内部是二分查找吧??查不到,这可凉凉。
正确姿势
意思就是,一定要判一下这个元素是不是存在,再取它的个数。这样从4000+ms ---> 100+ms
还有一些其他存法,比如bitset,因为40000*40000的地图是肯定开不下的嗷。。
于是
而256M的内存可以申请的bitset是8*1024*1024*256=2147483648,是能够开的下的
用的时候偏移一下
这样比map跑得更快
贴个简化的代码,能避开STL的坑点尽量避开吧
原文:https://www.cnblogs.com/NSD-email0820/p/9862226.html