《二分专题(题目讲解,附代码).》由会员分享，可在线阅读，更多相关《二分专题(题目讲解,附代码).（43页珍藏版）》请在金锄头文库上搜索。
1、以下是个人整理出的有关二分专题的题目， 代码有些头文件已删去， 为了减少代码长度（无大碍），希望对大家学习有所帮助！智商问题描述 Description某个同学又有很多小姊妹了他喜欢聪明的小姊妹 所以经常用神奇的函数来估算小姊妹的智商 他得出了自己所有小姊妹的智商小姊妹的智商都是非负整数 但是这个同学看到别的同学的小姊妹 也喜欢用神奇的函数估算一下 然后看看这个小姊妹在自己的小姊妹群体中排在第几位 . 输入格式 InputFormat第一行一个整数 N 代表小姊妹的个数第二行 N 个整数 代表这位同学 N 个小姊妹的智商 接下来若干行 每行一个整数 代表这位同学看中的别人的小姊妹的智商0=智商
2、 =2A31-10=N=1000000输出格式 OutputFormat输出若干行每行一个整数 回答新的小姊妹 在原来小姊妹中智商的排名样例输入51 2 3 4 512345样例输出12345主要矛盾就是那个Ov=n=1000000,没有这个一切都好说，但是如果没有这个, 就没有写的价值了。思想其实很简单，就是排个序，再二分。二分，只要计算Iog2(n)次，即可找出答案。而Iog2(100000020,实在是高 效得逆天。关于二分的讲解，在以前的日志最长不下降子序列中有讲。我奉 行动态规划的思想，同样的事不做第二遍。而现在，最主要的矛盾是排序。由于我怕出题人卡快排，于是就用堆排，而堆 排的时间
3、复杂度是n*log2(n)(又是二分的思想)，很稳定，卡不到虽说这道题在 TYVJ 上属于高级数据结构，但是其实它也没有用什么数据结构不过它的难度为 2 还是很合适。#include#includeconst int maxn=1000000;int n,k;int amaxn+10,bmaxn+10;void insert()int i=+k;while (i1 & ai1)int now=ai; ai=ai1; ai1=now;i=i1;void repair()a1=ak-;int i=1,j=2;if (j+1=k & aj+1aj) +j;while (j=k & ajai)int
4、now=ai; ai=aj; aj=now;i=j; j=j1;if (j+1=k & aj+1aj) +j;void read()freopen(sister.in,r,stdin); freopen(sister.out,w,stdout); scanf(%d,&n);for (int i=1; i=n; i+)scanf(%d,&ai);insert();for (int i=1; i=n; i+)bi=a1;repair();void work()int now;while (1)now = -1; scanf(%d, &now);if (now = -1) break; int l=
5、1,r=n,m;while (l1;if (now=bmid)r=mid-1;m=mid;elsel=mid+1;m=mid;if (now=bm) printf(%dn,m);else printf(%dn,m+1);int main()read();work();return 0;二分很简单，真的，不说了。我的程序是模块化的，可读性应该还可以教主的花园问题背景】LHX 教主最近总困扰于前来膜拜他的人太多了，所以他给他的花园加上了一道屏障。【问题描述】 可以把教主的花园附近区域抽像成一个正方形网格组成的网络， 每个网格都对应 了一个坐标(均为整数，有可能为负)，若两个网格(x1, yl, (
6、x2, y2有|x1 - x2| + |y1- y2| = 1，则说这两个网格是相邻的，否则不是相邻的。教主在 y = 0处整条直线上的网格设置了一道屏障，即所有坐标为 (x, 0)的网格。 当然，他还要解决他自己与内部人员的进出问题，这样教主设置了 N 个入口 a1, a2,aN可供进出，即对于y = 0上的所有网格，只有(a1, 0), (a2, 0) ，(aN, 0)可以通过，之外的所有纵坐标为 0的网格均不能通过，而对于(x, y)有 y 不为 0的网格可以认为是随意通过的。现在教主想知道，给定 M个点对(x1, y1, (x2, y2),并且这些点均不在屏障上，询 问从一个点走到另一
7、个点最短距离是多少，每次只能从一个格子走到相邻的格 子。【输入格式】输入的第1行为一个正整数N，为屏障上入口的个数。第2行有N个整数，a1, a2,aN，之间用空格隔开，为这N个入口的横坐标第3行为一个正整数M,表示了 M个询问 接下来M行，每行4个整数x1, y1, x2, y2有y1与y2均不等于0,表示了一个询 问从（x1, y1到 （x2, y2的最短路。【输出格式】输出共包含m行，第i行对于第i个询问输出从（x1, y1到（x2, y2的最短路距离是 多少。【样例输入】22 -120 1 0 -11 1 2 2【样例输出】42【数据规模】对于20%的数据，有n, mW 10, ai,
8、 xi, yi绝对值不超过100;对于40%的数据，有n, mW 100, ai, xi, yi绝对值不超过1000;对于60%的数据，有n, mW 1000, ai, xi, yi绝对值不超过100000对于100%的数据，有n, mW 100000 ai, xi, yi绝对值不超过100000000 这道题我一看就知道就知道了是用二分来查找，搞不懂为什么学长们就没有一 个能得到 60分以上。不多说了,这道题水。纵坐标直接绝对值相减就是了。 如果两个点都是在纵坐标的正半轴或是负半轴, 那根本不用通过路口, 横座标 也直接相减就是了。如果需要跨越屏障，那么找一个 a,让|x1-a|+|x2-a
9、|最小就是了。也就是找最 近的那几个,用二分就是了。本来刚开始还想过直接用 multiset。的,但是STL的调用时间我早就领教过了， 哆嗦了一下,还是用的手打二分。int n;const int maxn=100000;int amaxn+10;inline int find1(int x)int l=1,r=n,m;while (l1; if (amid=x)l=mid+1;m=mid;else r=mid-1;return am;inline int find2(int x)int l=1,r=n,m;while (l1; if (amid=x)r=mid-1;m=mid;else l=
10、mid+1;return am;inline void work()int x1,x2,y1,y2;scanf(%d%d%d%d,&x1,&y1,&x2,&y2);if (x1x2) swap(x1,x2);if (y10 & y20) | (y10 & y20)printf(%dn,abs(y2-y1)+abs(x2-x1);return;if (x1=an) printf(%dn,abs(y2-y1)+abs(x1-an)+abs(x2-an); return;if (find2(x1)=x2) printf(%dn,abs(y2-y1)+abs(x2-x1); return;int a1
11、=find1(x1),a2=find2(x2);int ans1=abs(y1-y2)+abs(x1-a1)+abs(x2-a1), ans2=abs(y1-y2)+abs(x1-a2)+abs(x2-a2);printf(%dn,min(ans1,ans2);int main()freopen(p1.in,r,stdin);freopen(p1.out,w,stdout);scanf(%d,&n);for (int i=1; i=n; i+)scanf(%d,&ai);sort(a+1,a+n+1);int m;scanf(%d,&m);for (int i=0; im; i+)work()
12、;fclose(stdin);fclose(stdout);return 0;软件 software【题目描述】一个软件开发公司同时要开发两个软件， 并且要同时交付给用户， 现在公司为 了尽快完成这一任务，将每个软件划分成 m 个模块，由公司里的技术人员分工 完成，每个技术人员完成同一软件的不同模块的所用的天数是相同的， 并且是已 知的，但完成不同软件的一个模块的时间是不同的， 每个技术人员在同一时刻只 能做一个模块， 一个模块只能由一个人独立完成而不能由多人协同完成。 一个技 术人员在整个开发期内完成一个模块以后可以接着做任一软件的任一模块。 写一 个程序，求出公司最早能在什么时候交付软件。
13、输入格式】100。接下来的 n 行每行包畲两个用空格隔开的整数 d1 和 d2：， d1 表示该技术 人员完成第一个软件中的一个模块所需的天数，d2表示该技术人员完成第二个软件中的一个模块所需的天数，其中iw d1, d2w 100。【输出格式】输出文件仅有一行包含一个整数d,表示公司最早能于d天后交付软件。【样例】software.in3 201 12 41 6software.out18【样例解释】最快的方案是第一个技术人员完成第二个软件的18个模块，用时 18天，第三个技术人员完成第一个软件的 18个模块， 用时 18天，其余的模块由第二个技术 人员完成，用时 12天，做完所有模块需要 18天。如果第一个技术人员完成第二 个软件的 17个模块， 第三个技术人员完成第一个软件的 17个模块， 其余的模块 由第二个技术人员完成，需要用时 18天，做完所有模块仍然需要 18天，所以少于 18 天不可能做完所有模块这个，一开始用的是三维的动规，用fijk表示前i个人，第一种软件生产了j 个，第二种生产了 k 个，花的最少时间。转移方程为：fijk=min(max(fi-1xy,(j-x)*d1+(k-y)*d2)。但这个方程的时间复杂度是
