二分专题(题目讲解,附代码)

1、以下是个人整理出的有关二分专题的题目，代码有些头文件已删去，为了减少代码长度（无大碍），希望对大家学习有所帮助！智商问题描述 Description某个同学又有很多小姊妹了他喜欢聪明的小姊妹 所以经常用神奇的函数来估算小姊妹的智商他得出了自己所有小姊妹的智商小姊妹的智商都是非负整数但是这个同学看到别的同学的小姊妹也喜欢用神奇的函数估算一下然后看看这个小姊妹在自己的小姊妹群体中排在第几位.输入格式 InputFormat第一行一个整数N 代表小姊妹的个数第二行N个整数 代表这位同学N个小姊妹的智商接下来若干行 每行一个整数代表这位同学看中的别人的小姊妹的智

2、商0<=智商<=231-10<=N<=1000000输出格式 OutputFormat输出若干行每行一个整数 回答新的小姊妹在原来小姊妹中智商的排名样例输入 51 2 3 4 512345样例输出 12345 主要矛盾就是那个0<=n<=1000000，没有这个一切都好说，但是如果没有这个，就没有写的价值了。    思想其实很简单，就是排个序，再二分。    二分，只要计算log2(n)次，即可找出答案。而log2(1000000）20，实

3、在是高效得逆天。关于二分的讲解，在以前的日志最长不下降子序列中有讲。我奉行动态规划的思想，同样的事不做第二遍。    而现在，最主要的矛盾是排序。由于我怕出题人卡快排，于是就用堆排，而堆排的时间复杂度是n*log2(n)（又是二分的思想），很稳定，卡不到。    虽说这道题在TYVJ上属于高级数据结构，但是其实它也没有用什么数据结构。不过它的难度为2还是很合适。#include<stdio.h>#include<stdlib.h>const int maxn=1000000;int n,k;

4、int amaxn+10,bmaxn+10; void insert()     int i=+k;     while (i>1 && ai<ai>>1)              int now=ai;  ai=ai>>1; ai>>1=now; &#

5、160;       i=i>>1;             void repair()     a1=ak-;     int i=1,j=2;     if (j+1<=k && aj+1<aj) +j;&

6、#160;        while (j<=k && aj<ai)              int now=ai; ai=aj; aj=now;         i=j;  j=j<<1;   &

7、#160;     if (j+1<=k && aj+1<aj) +j;             void read()     freopen("sister.in","r",stdin);     freopen("sister.out&

8、quot;,"w",stdout);     scanf("%d",&n);     for (int i=1; i<=n; i+)              scanf("%d",&ai);       &

9、#160; insert();              for (int i=1; i<=n; i+)              bi=a1;         repair();   

10、;    void work()     int now;     while (1)              now = -1;         scanf("%d", &now); &#

11、160;       if (now = -1) break;         int l=1,r=n,m;         while (l<=r)                &

12、#160;     int mid=(l+r)>>1;             if (now<=bmid)                        

13、60;     r=mid-1;                 m=mid;                         &

14、#160;                else                               l=mid+1;&

15、#160;                m=mid;                                &

16、#160;          if (now<=bm) printf("%dn",m);         else  printf("%dn",m+1);             int main() &

17、#160;  read();    work();return 0;   二分很简单，真的，不说了。我的程序是模块化的，可读性应该还可以。教主的花园【问题背景】LHX教主最近总困扰于前来膜拜他的人太多了，所以他给他的花园加上了一道屏障。 【问题描述】可以把教主的花园附近区域抽像成一个正方形网格组成的网络，每个网格都对应了一个坐标（均为整数，有可能为负），若两个网格(x1, y1)，(x2, y2)有|x1 x2| + |y1 y2| = 1，则说这两个网格是相邻的，否则不是相邻的。教主在y =

18、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)，并且这些点均不在屏障上，询问从一个点走到另一个点最短距离是多少，每次只能从一个格子走到相邻的格子。 【输入格式】输入的第1行为一个正整数N，为屏障上入口的个数。第2

19、行有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，m10，ai，xi，yi绝对值不超过100；对于40%的数据，有n，m100，ai，

20、xi，yi绝对值不超过1000；对于60%的数据，有n，m1000，ai，xi，yi绝对值不超过100000；对于100%的数据，有n，m100000，ai，xi，yi绝对值不超过100000000。 这道题我一看就知道就知道了是用二分来查找，搞不懂为什么学长们就没有一个能得到60分以上。    不多说了，这道题水。    纵坐标直接绝对值相减就是了。    如果两个点都是在纵坐标的正半轴或是负半轴，那根本不用通过路口，横座标也直接相减就是了。  

21、;  如果需要跨越屏障，那么找一个a，让|x1-a|+|x2-a|最小就是了。也就是找最近的那几个，用二分就是了。    本来刚开始还想过直接用multiset<>的，但是STL的调用时间我早就领教过了，哆嗦了一下，还是用的手打二分。 int n;const int maxn=100000;int amaxn+10; inline int find1(int x)    int l=1,r=n,m;    while (l&

22、lt;=r)            int mid=(l+r)>>1;        if (amid<=x)                    l=mid+1; &#

23、160;          m=mid;                              else  r=mid-1;    &#

24、160;         return am; inline int find2(int x)    int l=1,r=n,m;    while (l<=r)            int mid=(l+r)>>1;     &

25、#160;  if (amid>=x)                    r=mid-1;            m=mid;          &#

26、160;                   else  l=mid+1;              return am; inline void work()     int x1,x2,

27、y1,y2;     scanf("%d%d%d%d",&x1,&y1,&x2,&y2);     if (x1>x2) swap(x1,x2);         if (y1>0 && y2>0) | (y1<0 && y2<0)     &#

28、160;        printf("%dn",abs(y2-y1)+abs(x2-x1);         return;                    if (x1<=a1) &#

29、160;            printf("%dn",abs(y2-y1)+abs(x1-a1)+abs(x2-a1);         return;                  

30、;     if (x2>=an)              printf("%dn",abs(y2-y1)+abs(x1-an)+abs(x2-an);         return;         

31、              if (find2(x1)<=x2)              printf("%dn",abs(y2-y1)+abs(x2-x1);         return; 

32、;                             int a1=find1(x1),a2=find2(x2);     int ans1=abs(y1-y2)+abs(x1-a1)+abs(x2-a1),    

33、;     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",stdou

34、t);    scanf("%d",&n);    for (int i=1; i<=n; i+)        scanf("%d",&ai);    sort(a+1,a+n+1);       int m;    scan

35、f("%d",&m);    for (int i=0; i<m; i+)        work();    fclose(stdin);    fclose(stdout);return 0;软件software 【题目描述】    一个软件开发公司同时要开发两个软件，并且要同时交付给用户，现在公司为了尽快完成

36、这一任务，将每个软件划分成m个模块，由公司里的技术人员分工完成，每个技术人员完成同一软件的不同模块的所用的天数是相同的，并且是已知的，但完成不同软件的一个模块的时间是不同的，每个技术人员在同一时刻只能做一个模块，一个模块只能由一个人独立完成而不能由多人协同完成。一个技术人员在整个开发期内完成一个模块以后可以接着做任一软件的任一模块。写一个程序，求出公司最早能在什么时候交付软件。【输入格式】    输入文件第一行包含两个由空格隔开的整数n和m，其中1n100,1m100。接下来的n行每行包畲两个用空格隔开的整数d1和d2：，d1表示该技术人员完成第一个软件

37、中的一个模块所需的天数，d2表示该技术人员完成第二个软件中的一个模块所需的天数，其中ld1，d2100。【输出格式】    输出文件仅有一行包含一个整数d，表示公司最早能于d天后交付软件。【样例】 software.in 3 20 1 1 2 4 1 6 software.out 18【样例解释】    最快的方案是第一个技术人员完成第二个软件的18个模块，用时18天，第三个技术人员完成第一个软件的18个模块，用时18天，其余的模块由第二个技术人

38、员完成，用时12天，做完所有模块需要18天。如果第一个技术人员完成第二个软件的17个模块，第三个技术人员完成第一个软件的17个模块，其余的模块由第二个技术人员完成，需要用时18天，做完所有模块仍然需要18天，所以少于18天不可能做完所有模块。     这个，一开始用的是三维的动规，用fijk表示前i个人，第一种软件生产了j个，第二种生产了k个，花的最少时间。转移方程为：fijk=min(max(fi-1xy,(j-x)*d1+(k-y)*d2)。但这个方程的时间复杂度是(n5)的，只能过6组数据。    

39、然后看题解，是先二分答案，再动规。设当前二分的中点是mid，然后用fij表示前i个人，生产第一种软件j个，然后最多可以生产多少个第二种软件。fij=max(fi-1j-k+(mid-k*d1)/d2)。k=min(mid/d1,j)。    二分就可以了。把二分的右界设成0x7ffffff，也很快就过了。    这种类型的题要多留心，应该一眼就看出它是二分，这样才好。    Code:int n,m;const int maxn=100;int f2maxn+10,amaxn

40、+10,bmaxn+10; bool dp(int mid)     memset(f,-1,sizeof(f);     int now=0,pas=1;     fnow0=0;         for (int i=0; i<n; i+)        &#

41、160;     swap(pas,now);         for (int j=0; j<=m; j+)             for (int k=0; k<=min(mid/ai,j); k+)         &#

42、160;       if (fpasj-k != -1)                                      int tmp=

43、(mid-k*ai)/bi;                     fnowj=max(fnowj,fpasj-k+tmp);                      

44、;                         return (fnowm >= m ? 1 : 0);  int main()    freopen("software.in","r",stdin);   &

45、#160;freopen("software.out","w",stdout);    scanf("%d%d",&n,&m);    for (int i=0; i<n; i+)        scanf("%d%d",&ai,&bi);       

46、;    int l=0,r=0x7ffffff,ans;    while (l<=r)            int mid=(l+r)>>1;        if (dp(mid)         

47、0;          r=mid-1;            ans=mid;                         

48、   else  l=mid+1;                 printf("%dn",ans);    fclose(stdin);    fclose(stdout);return 0;二分/最短路收费站cost【题目描述】在某个遥远的国家里，有n个城市。编号为1，2，

49、3，n。这个国家的政府修建了m条双向的公路。每条公路连接着两个城市。沿着某条公路，开车从一个城市到另一个城市，需要花费一定的汽油。开车每经过一个城市，都会被收取一定的费用（包括起点和终点城市）。所有的收费站都在城市中，在城市间的公路上没有任何的收费站。小徐现在要开车从城市u到城市v(1<=u，v<=n)。她的车最多可以装下s升的汽油。在出发的时候，车的油箱是满的，并且她在路上不想加油。在路上，每经过一个城市，她要交一定的费用。如果她某次交的费用比较多，她的心情就会变得很糟。所以她想知道，在她能到达目的地的前提下，她交的费用中最多的一次最少是多少。这个问题对于她来说太难了，于是她找到

50、了聪明的你，你能帮帮她吗？【输入格式】第一行5个正整数，n，m，u，v，s。分别表示有n个城市，m条公路，从城市u到城市v，车的油箱的容量为s升。接下来有n行，每行1个正整数，fi。表示经过城市i，需要交费fi元。再接下来有m行，每行3个正整数，ai，bi，ci(1<=ai，bi<=n)。表示城市ai和城市bi之间有一条公路，如果从城市ai到城市bi，或者从城市bi到城市ai，需要用ci升汽油。【输出格式】仅一个整数，表示小徐交费最多的一次的最小值。如果她无法到达城市v，输出-1。【输入样例1】4 4 2 3 8856102 1 22 4 11 3 43 4 3【输出样例1】8【输

51、入样例2】4 4 2 3 3856102 1 22 4 11 3 43 4 3【输出样例2】-1【数据范围】    对于60%的数据，满足n<=200，m<=10000，s<=200对于100%的数据，满足n<=10000，m<=50000，s<=1000000000对于100%的数据，满足ci<=1000000000，fi<=1000000000，可能有两条边连接着相同的城市。       去年5月刚学图论时完对这道题完全没有概念，被虐

52、得瓜兮兮的。    现在一看就知道要二分。只是还是有一组超时了，没办法了。    二分收费，然后用spfa，凡是fi小于等于当前收费的，就进行松弛，然后看disv，如果小于等于s，即可行。    Code: int n,m,u,v,s;const int maxn=10000;struct point       int x,l;     

53、0; point *next;       *pmaxn+10;int fmaxn+10,dismaxn+10,amaxn+10;bool hashmaxn+10;int q5000000; void insert(int u,int v,int l)     point *now=new point;     now->x=v;  now->l=l;  

54、   now->next=pu;  pu=now;  void read()     freopen("cost.in","r",stdin);     freopen("cost.out","w",stdout);     scanf("%d%d%d%d%d",&

55、n,&m,&u,&v,&s);     for (int i=1; i<=n; i+)         scanf("%d",&fi),ai=fi;     while (m-)              

56、;int a,b,c;         scanf("%d%d%d",&a,&b,&c);         insert(a,b,c);         insert(b,a,c);        

57、0;       sort(a+1,a+n+1);  bool spfa(int a)     memset(dis,0x3f,sizeof(dis);     memset(hash,0,sizeof(hash);     if (fu>a) return 0;     disu=0; &#

58、160;hashu=1;     int l=0,r=0;     qr+=u;         while (l<r)              int x=ql+;        

59、 hashx=0;                 for (point *i=px; i; i=i->next)             if (fi->x<=a && disi->x>disx+i->l)  

60、60;                           disi->x=disx+i->l;                 if (!hash

61、i->x)                                      hashi->x=1;        &#

62、160;            qr+=i->x;                                   &#

63、160;                                         return (disv <= s ? 1 : 0);  void wor

64、k()     if (!spfa(an)  printf("%dn",-1);     else              int l=1,r=n,m;         while (l<=r)  &#

65、160;                   int mid=(l+r)>>1;             if (spfa(amid)           &

66、#160;                  r=mid-1;                 m=mid;            

67、;                               else  l=mid+1;               

68、;         printf("%dn",am);          fclose(stdin);     fclose(stdout);  int main()    read();    work();return 0;最长上升子序

69、列（二分优化）【题目描述】    LIS问题是最经典的动态规划问题之一，这是一个加强版的问题。    对于一个长度为N的序列，要求它的一个上升子序列，这个上升子序列必须包含第K个元素。    例如：对于长度为6的序列2 7 3 4 8 5，其最长上升子序列是2 3 4 5，但如果限制一定要包含第二个元素，那满足此要求的最长上升子序列就是2 7 8。【输入格式】    第一行两个数N，K。N<=200,000  

70、  第二行N个数，为此序列。【输出格式】    包含第K个元素的最长上升子序列的长度。【输入样例】8 665 158 170 299 300 155 207 389【输出样例】4     其实，一定要包含第K个元素也是很好解决的，但最麻烦的就在于其数据范围。对于200,000的规模，普通的(n2)的算法是不行的，只能用来对拍。对于这种数据，算法的时间复杂度必须在(nlog(n)及以下才行。    我们用fi表示包含第i个数的最长上升子序列的长度，

71、再用gi表示长度为i的最长上升子序列，最后一个数的最小值。这样用二分查找到一个gl，使gl-1小于ai，而gl大于等于ai，这样使l最大，fi=l。找到后再更新gl的值。这样就不会破坏gi的单调性。同样的方法也可以倒过来用。这样的时间复杂度就是(nlog(n)。所谓的LIS问题的二分优化。当然理论上也可以用STL中的<map>来完成这种工作，但是我不是很放心<map>的调用速度。    前天晚上整了很久，因为各种人品差，一直连对拍都没能过。还是昨天晚上才整好的。    Code:int n,

72、k;const int maxn=200000;int amaxn+10,fmaxn+10,gmaxn+10; int dp1()    memset(g,0x3f,sizeof(g);    g0=0;    for (int i=1; i<=k; i+)            int l=0,r=n,m;   

73、;     while (l<=r)                    int mid=(l+r)>>1;            if (gmid>=ai)    

74、;                        r=mid-1;                m=mid;       

75、60;                                 else  l=mid+1;            

76、60;         fi=m;  gm=ai;        return fk; int dp2()    memset(g,0,sizeof(g);    memset(f,0,sizeof(f);    g0=0;    for

77、(int i=n; i>=k; i-)            int l=0,r=n,m;        while (l<=r)                    int mid=(

78、l+r)>>1;            if (gmid<=ai)                            r=mid-1;   

79、0;            m=mid;                                    

80、0;    else  l=mid+1;                      fi=m;  gm=ai;        return fk; int main()   

81、60;freopen("lis.in","r",stdin);    freopen("lis.out","w",stdout);    scanf("%d%d",&n,&k);    for (int i=1; i<=n; i+)        scanf("%d&

82、quot;,&ai);           int ans=dp1();    ans+=dp2();    printf("%dn",ans);    fclose(stdin);    fclose(stdout);return 0;划分数列【题目描述】给你一个有n个元素的数列，要求把它划分成k段

83、，使每段元素和的最大值最小【输入格式】第一行两个正整数n，k第二行为此数列ai【输出格式】一行一个数，为题目所求答案【样例输入】5 22 1 3 4 5【样例输出】9【数据规模】30%数据 n <= 30, k <= 10100%数据 n <= 100000, k <= n, ai <= 109150%数据 n <= 100000, k <= n, |ai| <= 109(附：这50分超越了noip难度，大家可以无视）【时限】1s     最大值最小，这种类型的题90

84、%都可以用二分。我学OI快两年了，学二分一年了，只见过一个反例。    二分答案，看是否可以划分出来即可。此题的难点在于如何判断是否能划分，而不在于二分。    Code: int n,k;const int maxn=100000;int amaxn+10;long long sum,Max; void read()     freopen("seq.in","r",stdin);  

85、   freopen("seq.out","w",stdout);     scanf("%d%d",&n,&k);         for (int i=1; i<=n; i+)              

86、scanf("%d",&ai);         sum+=(long long)ai;         Max=max(Max,(long long)ai);       bool can(long long x)     long long temp=0ll;

87、0;    int num=0;     for (int i=1; i<=n; i+)              temp+=(long long)ai;         if (temp<=x && temp+(long long)ai+1>

88、x)                      temp=0ll;  num+;                       &#

89、160;      if (num=k && i<n) return 0;          return 1; void work()     long long l=Max,r=sum,m;     while (l<=r)      &

90、#160;       long long mid=(l+r)>>1;         if (can(mid)                      r=mid-1;   

91、          m=mid;                               else l=mid+1;      

92、;              cout<<m<<endl;     fclose(stdin);     fclose(stdout); int main()    read();    work();return 0;奶牛晒衣服【题目描述】&#

93、160;   在熊大妈英明的带领下，时针和它的同伴生下了许多牛宝宝。熊大妈决定给每个宝宝都穿上可爱的婴儿装。于是，为牛宝宝洗晒衣服就成了很不爽的事情。    圣人王担负起了这个重任。洗完衣服后，你就要弄干衣服。衣服在自然条件下用1的时间可以晒干A点湿度。抠门的熊大妈买了1台烘衣机。使用烘衣机可以让你用1的时间使1件衣服除开自然晒干的A点湿度外，还可烘干B点湿度，但在1的时间内只能对1件衣服使用。    N件的衣服因为种种原因而不一样湿，现在告诉你每件衣服的湿度，要你求出弄干所有衣服的最

94、少时间（湿度为0为干）。【输入格式】    第一行N，A，B；接下来N行，每行一个数，表示衣服的湿度(1湿度，A，B500000，1N500000)。【输出格式】    一行，最少时间。【输入样例】3 2 11 2 3【输出样例】1    首先可以明确一点，假设我们花X的时间可以弄干全部衣服，那么我们花X+1的时间也必然可以弄干所有衣服。这就为二分创造了条件。    其次，各时间段是互不干扰的，所

95、以，判断的依据就是：假设当前的二分中点是X，那么对于在X内就可以晒干的，就不管了；如果在X内晒不干的，那就计算出要烘干多少次，最后累加，看总的烘干次跟X的大小关系，如果小于等于，说明在X内可以搞定；否则即搞不定。    Code: int n,a,b;int d500010; bool judge(int x)     int tmp=0;     for (int i=0; i<n; i+)   &

96、#160;          if (di<=a*x) continue;         int y=di-a*x;         tmp+=(y+(b-1)/b;            &

97、#160; return (tmp <= x ? 1 : 0);  int main()    freopen("dry.in","r",stdin);    freopen("dry.out","w",stdout);    scanf("%d%d%d",&n,&a,&b);   

98、60;for (int i=0; i<n; i+)        scanf("%d",&di);       int l=1,r=500000,ans;    while (l<=r)            int mid=(l+r)>>

99、;1;        if (judge(mid)            r=mid-1,ans=mid;        else  l=mid+1;            

100、60;    printf("%dn",ans);    fclose(stdin);    fclose(stdout);return 0;文明的复兴【题目描述】    战神Prince&Gush回归了，但许多原先的上层精灵越来越不安分。他们无法忍受失去权力的空虚感，开始重新寻找新的途径获取权利。他们直率急躁的领导人King_Bette开始公开抨击权威，并散布谣言。权利的统治需要统一，需要强硬，被逼无奈下正

101、义的领袖开始收缴反动的资料，清除世界的毒瘤，借以踏上快速发展之路。    不良信息指的是一组单词，每个单词均为不良信息。不良信息文本是指包含一系列的单词，且其中包含有不良信息。发布信息者经常在单词中加些字母以外的字符以搅乱正义的视线，于是Prince想请你为他写一个能够将这些不良信息屏蔽掉的工具。但是为了尽量降低误删率,他提出了下面一个要求：你只需要将字母完全匹配的单词屏蔽掉即可。    例如:    sex为不良信息时,sex8,sex$,se#x均为不良信息sexx 则不

102、属于不良信息.【输入格式】    第一行为一个正数k <= 10000，表示有k个需要被屏蔽的词语，均为小写字母。    以下k行每行一个单词。    最后一行为输入需要处理的文本（文本长度<=100000）,单词与单词之间空格分开且所有字母为小写字母。【输出格式】    输出一行和输入格式一致的文本，被屏蔽的单词的字母以*代替原字母。【输入样例】1sexsex sex8 sex$ s&&ex sexx aa

103、a bbb【输出样例】* *8 *$ *&&* sexx aaa bbb     题目的意思是，如果把一个单词中的各种符号去掉以后，如果它是一个敏感词，那就要屏蔽。必须要跟一个敏感词完全一样才可以。    所以我们可以先处理出每个单词中的小写字母，然后再枚举敏感词，如果有一样的，那就屏蔽输出；找不到，就直接输出。    因为敏感词最多有10000个，所以要先排序，再用二分查找，以提高效率。    但因为数据是欧

104、教自己做的，所以很坑。经常出现一个敏感词中一个字母也没有的情况（就是一行只有一个回车），C+的同学都被坑惨了。    Code: int k,n;char list10010260; int cmp(const void *a,const void *b)    return strcmp(char *)a,(char *)b); void read()     freopen("words.in","r&

105、quot;,stdin);     freopen("words.out","w",stdout);     scanf("%d",&k);     char now260,a=getchar();     while (k-)        

106、0;     a=getchar();         if (a='n') continue;         int l=0;         memset(now,0,sizeof(now);     

107、60;   while (a!='n')                      nowl+=a;             a=getchar();    

108、60;                   memcpy(list+n,now,sizeof(now);                qsort(list+1,n,sizeof(list0),cmp);  void work()

109、     char a5000;    while (scanf("%s",&a) != EOF)            char b5000;        memset(b,0,sizeof(b);      

110、0; int k=0;        for (int i=0; i<strlen(a); i+)            if (int)ai>96 && (int)ai<123) bk+=ai;             &#

111、160; int l=1,r=n,m;        while (l<=r)                    int mid=(l+r)>>1;           

112、0;if (strcmp(listmid,b)<=0)                            l=mid+1;               

113、0;m=mid;                                                

114、0;  else  r=mid-1;                             if (strcmp(b,listm)!=0) printf("%s",a);      

115、60; else                    for (int i=0; i<strlen(a); i+)                if (int)ai>96 && (int)ai<

116、;123) printf("%c",'*');                else  printf("%c",ai);                printf(" ");

117、60;                fclose(stdin);    fclose(stdout);  int main()    read();    work();return 0;二分/搜索软件下载【题目描述】    ICG大赛马上就要举行了，作为大

118、赛的组委会兼参赛选手，信息组的成员们当然要做准备了，而其中十分重要的一项准备工作就是下载很多举办大赛必不可少的软件，已知现在机房有N台电脑，组委会列出了M个需要下载的软件及其大小Ai（即需要下载的时间），每个电脑同一时间只能下载一个软件，一个软件也只能由一个电脑下载，每个电脑下载速度相同且互不影响.因为有神器Cena的存在，每个软件只需由某一台电脑下载一次就能使整个机房的电脑普及该软件。现在ICG组委会想知道最快能在多长时间内下载完成。【输入格式】    第1行：两个整数N、M，分别代表机房的电脑数及需要下载的软件数量。   

119、; 第2行：M个整数，第i个整数表示Ai的值。【输出格式】    一行一个整数，表示能下载完所有软件的最短时间。【输入样例】2 31 2 3【输出样例】3     又见最大值最小问题，二分。    本质上就是把m个数分成小于等于n份，让它们每一份的和的最大值最小。    只不过这是用搜索来验证的。因为顺序可以乱的，所以不好用动规。    先来排一次一序，先下大的软件，再下小的。

120、    只是至今不明白，那个理论时间复杂度为阶乘级的深搜，为什么那么快呢？    dis(x,y,z,mid)，表示分了x份，共用了y个数，总共还剩下z的时间，并且当前的二分中点为mid，加上这个减枝：(n-x+1)*mid-stax    因为它不用完全遍历，所以实际上的时间复杂度较低。    Code: int n,m,ans,sum;int a55,sta15;bool hash55; int cmp(cons

121、t void *a,const void *b)    return (*(int*)a > *(int*)b ? -1 : 1); bool dfs(int x,int y,int z,int mid)     if (m-x+1)*mid-stax<z)  return 0;     if (y=n)  return 1;      

122、;   for (int i=1; i<=n; i+)         if (!hashi)                      if (stax+ai<=mid)