10.24正式程序员节,在这一天发布我的第一篇博客好不浪漫!!!
OK!进入正题,这篇文章我们将分析牛客挑战赛53A题----乃智哥哥的小迷题,ccf第43题----矩形分割,及二者共同的算法---二分法。良好的阅读指南————
- 先分享二分法的基本应用;
- 再放题,在每次提前会将一些隐蔽的坑点先做提醒,以免浪费太多时间:
- 在尝试做题;
- 一起分析题目,找到除二分之外两道题的特点;
- 在总结二分法。
好,让我们先来认识一下二分法。最简单的二分法就是二分查找里面的了。与我们初中数学,及高中的二分近似估计零点思想相同。
基础二分法如题:在一个有序数组中0、1、2、3、4、5、6、7、8中找到8是否存在,并输出下标;
#includeint get_k(int x[], int y,int z)//自定义一个函数实现二分查找 { int mid; int l = 0; int r=z-1;//0是数组左边值,z-1为最右边下标(因为最左边下标为0,所以右边为z-1) while (l <= r) { mid = (l + r)/ 2; if (x[mid] < y) l = mid + 1; else r = mid - 1; } mid = (l + r)/ 2; return mid;//返回中间值; } int main() { int a[10] = { 0,1,2,3,4,5,6,7,8 }; int k = 8; int r = sizeof(a) / sizeof(a[1]); //数组字节数比上单个字符字节数=字符个数; int b = get_k(a,k,r);//输入数组,查找值,数组长度; printf("%d", b); return 0; }
如果按从一开始注意查找的思路,我们需要查找八次才可以找到;而用二分法仅用三次。如果遇到数据为10的8次方之类的,前者的计算量会十分大,更会引起超时。
本想详细展开说二分的原理,但是辅以画图会更好理解,奈何上传不便,小可爱们可以自己画图,这里也附上大佬关于二分的详细解答:数据结构专题(一)二分法,寻找解题思路看这一篇就够了_余光的博客-CSDN博客_二分法
这里说一个小技巧,解题之前我们先看一下数据范围,如果十分之大,因为运行有时间限制,那它多半就要用一些减少时间复杂度的算法了,这其中就有二分法。
到这里,我们已经简单认识了二分,那让我们来看题吧。
乃智哥哥的小迷题 提示 思路篇这个题需要先看到其中的端倪。
我们可以先想,恰好到是什么情况?比如到1?到3?到6?
让后在想,如果在刚好点的前一步怎么办,比如2?怎么到呢?在3的基础上退一步即可。
再想,那前两步呢怎么办?刚才是到恰好点后再退,那再到之前的步数先退呢?好,思路就像提示到这里。
代码篇题目的数据范围可是10的15次方啊,即使用二分法,那在1~x中找,x为10的15次方依旧会超时;该怎么办?我们真的有必要在x里找吗?右端点究竟是什么?x/2?x的平方根?还是什么?
解题如嫌看文字版的慢的话可以去牛客上搜索“牛客挑战赛53”智乃哥哥的页面!或哔哩哔哩上搜索!!
好了,来上代码!
#includeint main() { long long x[100005]; int T; scanf("%d",&T); int i; long long mid; for(i=0;i =x[i]) r=mid; else l=mid+1; } mid=l+(r-l)/2; if(mid*(mid+1)/2==x[i]+1) printf("%lldn",mid+1); else printf("%lldn",mid); } return 0; }
跟你的一样吗?一样。啊,你说超时了,哦哦哦,放错了,嘿嘿。再来!
#includeint main() { long long x[100005]; int T; scanf("%d",&T); int i; long long mid; for(i=0;i =x[i]) r=mid; else l=mid+1; } mid=l+(r-l)/2; if(mid*(mid+1)/2==x[i]+1) printf("%lldn",mid+1); else printf("%lldn",mid); } return 0; }
有什么区别吗?我们看到2里出现了1e8,不会有小可爱和我一样不知道1e8是什么吧?就是10的8次方啦!
思路:一直向前走不考虑回头的话,比如第4步,到了x=10;那这时如果要求x=12怎么办,肯定得先跑到再说。第5步就到15。也就是说第一步,肯定要先到>=目标点的地方。
到了之后恰好为就直接输出了,但需要退步的话,退一步当然只需要步数再加1即可;
那退多步该如何实现?退一步是在到之后退步,那我们不妨考虑一下到之前退步。
如果第一步退步的话,
原本:1+2+3+4+5=15
之后:-1+2+3+4+5=?
我们看到虽然退一步,实则退2步;那在第二步退呢?
原本:1+2+3+4+5=15
之后:1-1+3+4+5=12
实则退了3步;以此类推我们可以看到,之前退的话,会退2,3,4…
也就是大于一步的我们可以通过之前退步来实现!
如x=12,先第5步大于等于12,在通过第二步退步,来满足12;其为:1-1+3+4+5=12,实则还是5步。
我们可以得出结论,
先到再说;
再考虑退步;
不许退步就是到达步数;
退大于2步的也是到达步数;
退一步为到达步数加1;
那么问题转化为找几步之后可以到达;
当然要用到等差数列的前n项和,S=n*(n+1)/2
这也就解释了我们右端点为什么取1e8了;S近似为n^2了,x最大也才10^15,我们取10^8绰绰有余。就不用从1~x如此麻烦了,这种思想也会经常用到,还需多多留意。
有朋友或许想到了如果我右端点去x的平方根会更好,对,毕竟x并不会次次为1e15.但是因为用了sqrt后其为double型,转换麻烦,可能会强制类型转换,而且如果开根号后无法取整,变为整形实则变小了,不如1e8一劳永逸。
关于二分我们稍后总结一并再说。
矩形分割(这个题我的思路后边有点麻烦,期待有小可爱可以分享你的更好的解法,同时也鼓励大家一起写自己的博客)
提示 思路篇这个好理解,我们无非找到一个临界的x使x-1时左边面积<右边,在x时左边>=右边,此时的x一定是使左右差最小的时刻,而这种不断逼近找临界点的正是二分的拿手好戏。
但是不要忽视了最后一句话“使左边大矩形面积尽可能大”,而我们找到的仅仅是临界值,如果这个临界值并不穿过某个小矩形,(即为即使x右移些许,并不影响左右面积差,既可以使左大矩形面积更大)那该怎么找呢?
在提示,在到临界点之后找逼近点,莫要加1加1一个一个判断,我们使用二分不就是为了避免这种情况的嘛!莫要问我怎么知道的,我也这样过来的。所以我用了两次二分,不知道可不可以改进?期待分享!
解题上代码!
#includeint get_s(int x,int L[],int T[],int W[],int H[],int n)//自定义函数,来求左右面积差 { int i; int sl = 0; int sr = 0; for (i = 0; i < n; i++) { if (L[i] + W[i] <= x) sl += W[i] * H[i]; else if (L[i] >= x) sr += W[i] * H[i]; else { sl += (x - L[i]) * H[i]; sr += (L[i] + W[i] - x) * H[i]; } } return sl - sr; } int main() { int R; scanf("%d", &R); int N; scanf("%d", &N); int l[10005], t[10005], w[10005], h[10005]; int i; for (i = 0; i < N; i++) { scanf("%d%d%d%d", &l[i], &t[i], &w[i], &h[i]); } int le = 0; int r = R; int mid; while (le < r) { mid = (le + r) / 2; if (get_s(mid, l, t, w, h, N) >= 0) r = mid; else le = mid + 1; }//求临界值 mid = (le + r) / 2; int b = get_s(mid, l, t, w, h, N); if (get_s(mid + 1, l, t, w, h, N) != b) printf("%d", mid);//如果x过了某个矩形则直接输出 else { le = mid; r = R; while (le < r) { mid = (le + r) / 2; if (get_s(mid, l, t, w, h, N) > b) r = mid; else le = mid + 1; }//使用二分法来求逼近点 mid = (le + r) / 2; if (mid == R) printf("%dn", mid);//吃了1000 1 1 1 2 1的亏; else printf("%d", mid - 1); } return 0; }
可以看到,敲代码上没有太出人意料的小细节;
来解释一下最后的输出;当时提交的我遇到了尴尬的问题
我们看到,错误的仅与正确结果相差1,这提醒我,我们求的逼近点其实是逼近点以前满足临界点的面积差,但逼近点已经不满足了,需要-1;然后就更尴尬了
这是一山不容二虎啊,70不容30 ,这两种情况一定是对立的;
我又想到当临界点的右方没有小矩形了,如输入为
1000
1
1 1 1 1
那其实就1个矩形,逼近点直接是右端点了,那就没有前者-1那一说了,所以分了两种情况输出。
总结二分我们可以看到,题中二分与最开始的二分查找有一些细节上的不同,如l 还有我师傅给的两个模板 如果你看了开始推荐的大大佬的博客,更有三种情况,实在纷繁复杂。师傅说,平时用他给的两种就可解决大部分问题了,至于其他的我也很迷呼,有大佬可以为我讲解吗? 至于师傅的两种,(l+r+1)/2与后面的l=mid+1则是为了防止死循环,拿0 和1试一下,会发现 如果不这样的话会一直在0 1中,跳不出来。 夜已深没想到已经写了快5千字,第一次还是比较多吧。感觉并没有阐述太清,太过仓促,毕竟打字效率还是太低。敲代码还是一个挺让人自我否定的,每个题要写好久,有时一个晚上都没解出一个来。从10.1到现在,已经敲了三千多行代码,作为一个刚接触的小白,确实挺让人崩溃的。好多天,连着写不出来,甚至都让我怀疑为什么要选择这个专业。如果你也是这样,不要慌张。外教社新编大学英语unit2,Why you feel busy里面写的让我缓解了焦虑的情绪。 同时程序员多坐,记得多运动,多喝水,照顾还易秃头的我们! 节日快乐! 晚安! 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)