2020年5月第一周

2020年5月第一周

学习内容

二分查找法的思想非常简单，在一组已经完成排序的数据(array[])中，如果需要查找某一特定数据（value）是否存在的时候，设置两个上下限（max， min）开始的时候在数组的最前和最后，把需要查找的值跟这两个位置的中间位置数据(array[(max+min)/2])进行对比，如果value >array[(min+max)/2] ,则缩小范围使得min=(min+max)/2,反之，如果value<array[(min+max)/2],则缩小范围使得max=(min+max)/2。持续缩小范围，知道找到对应的值的位置或者min==max,也就是数组中不存在该值。

这种做法有什么好处呢。在一个单调区间里查找答案，在正常的思维下都是用暴力枚举。比如说有几个不同大小的球，它们的直径为1，2，3，4，5，10，20，让你从中找出直径为10cm的那一个球。
一般人都会这样做：从头到尾一个一个的量，直到找到答案为止，这样复杂度最坏情况下为O（n），我们有没有更快的方法呢？
答案就是用二分，先从区间里找排在中间的元素，找到第四个元素为4，发现4比10小，所以答案应该在第四个元素的后面。然后再从第五位到最后一位的区间里找排在中间的元素，找到第六个元素10。OK，问题解决，只用了两次，复杂度为O（log n），优化了很多。

二分答案，就是用二分的方法，在可能的答案区间里找出问题的答案，大多数情况下用于求解满足某种条件下的最大（小）值，前提是答案具有单调性，同时也可以理解为是一种倒推方法（先找答案在判断答案是否可行、有没有更优解）。

    int l=1,r=ll;while(l<=r){int mid=(l+r)>>1;if(check(mid)>m)r=mid-1;else l=mid+1;}

题目解决

题目

一年一度的“跳石头”比赛又要开始了!

题目描述

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。

输入输出

输入：
第一行包含三个整数 L,N,M ，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证L≥1 且 N≥M≥0 。

接下来 N 行，每行一个整数，第 i 行的整数 Di( 0 < Di < L)， 表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出：
一个整数，即最短跳跃距离的最大值。

输入输出样例

输入样例
25 5 2
2
11
14
17
21
输出样例
4
说明

输入输出样例 1 说明：将与起点距离为 2 和 14 的两个岩石移走后,最短的跳跃距离为 4 (从与起点距离 17 的岩石跳到距离 21 的岩石,或者从距离 21 的岩石跳到终点)。

另：对于20% 的数据, 0≤M≤N≤10 。

对于 50% 的数据,0≤M≤N≤100 。

对于 100% 的数据, 0≤M≤N≤50,000,1≤L≤1,000,000,000 。

这个题是让你求最短跳跃距离的最大值，很明显，是一个二分答案题。

这里的check实际上是一种贪心的策略，因为有一点是可以确定的：拿走的石头越多，最短跳跃距离越大（当然拿石头是有一定策略的）。因为有拿石头的限制，所以也要让在符合条件下拿走的石头最少。

ans为拿走的石头数量，t为上一块石头的位置，如果两块石头的间距小于最小距离，就把这块石头移走，更新后面一块石头的位置 ans++,i++;如果以当前的mid为最小跳跃距离时，要拿走的石头比限定的要多，说明mid的值大了，就要更新右边界，继续查找

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<cmath>
#include<iomanip>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
#define PI acos(-1)
int ll,m,n,a[50005];
using namespace std;
int check(int x)
{int ans=0,t=0;for(int i=1;i<=n;i++){while(a[i]-t<x&&i<=n)ans++,i++;t=a[i];} return ans;
}
int main()
{scanf("%d%d%d",&ll,&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);a[++n]=ll;int l=1,r=ll;while(l<=r){int mid=(l+r)>>1,q=check(mid);if(q>m)r=mid-1;else l=mid+1;}printf("%d",r);return 0;
}

Description
The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .
Input
The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 2 28 ) that belong respectively to A, B, C and D .
Output
For each input file, your program has to write the number quadruplets whose sum is zero.
Sample Input
6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45
Sample Output
5
Hint
Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).

这个题解起来效率比较低，题意是求矩阵里有多少组四个相加等于0，可以把矩阵分成两列12,34，然后12枚举求和，34枚举求和，由于没有顺序可以排下序然后从sum34里二分查找与sum12和为0的数，cnt++，在暴力求解的基础上稍微改进了一下，但是效果依旧不算理想

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<cmath>
#include<iomanip>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
#define PI acos(-1)
int a[4002][4],sum12[16000002],sum34[16000002];
int main()
{int n,mid;while(~scanf("%d",&n)){for(int i=0; i<n; i++){scanf("%d%d%d%d",&a[i][0],&a[i][1], &a[i][2],&a[i][3]);}int k=0;int m=0;for(int i=0; i<n; i++)for(int j=0; j<n; j++){sum12[k++]=a[i][0]+a[j][1];sum34[m++]=a[i][2]+a[j][3];}sort(sum34,sum34+k);int cnt=0;for(int i=0; i<k; i++){int left=0;int right=k-1;while(left<=right){mid=(left+right)/2;if(sum12[i]+sum34[mid]==0){cnt++;for(int j=mid+1;j<k;j++){if(sum12[i]+sum34[j]!=0)break;elsecnt++;}for(int j=mid-1;j>=0;j--){if(sum12[i]+sum34[j]!=0)break;elsecnt++;}break;}if(sum12[i]+sum34[mid]<0)left=mid+1;elseright=mid-1;}}printf("%dn",cnt);}return 0;
}

Description

Given N numbers, X1, X2, ... , XN, let us calculate the difference of every pair of numbers: ∣Xi - Xj∣ (1 ≤ i ＜ j ≤ N). We can get C(N,2) differences through this work, and now your task is to find the median of the differences as quickly as you can!

Note in this problem, the median is defined as the (m/2)-th  smallest number if m,the amount of the differences, is even. For example, you have to find the third smallest one in the case of m = 6.

Input

The input consists of several test cases.
In each test case, N will be given in the first line. Then N numbers are given, representing X1, X2, ... , XN, ( Xi ≤ 1,000,000,000  3 ≤ N ≤ 1,00,000 )

Output

For each test case, output the median in a separate line.

Sample Input

4
1 3 2 4
3
1 10 2

Sample Output

1
8

题目大意：给你n个数，任意两个数之间的差共有m=(n-1)*n/2种然后让你输出这些数中间的那一个，规则为 若m为奇数，中间的那一个为第（m+1)/2小的数,若m为为偶数，中间那个数指的是第m/2小的数。

思路分析：采用二分算法，因为a[i]-a[j]是取了绝对值的，因此就相当于是大的减小的，因此可以将数组a[n]先sort排序，然后 根据差值确定二分范围，我确定的是0~a[n-1]-a[0],然后开始二分搜索，而check函数则主要是统计比a[i]+d小的 数有多少个，如果>=（m+1）/2就return true else return false,而在统计的过程中如果用传统的顺序查找肯定也会导致超时，所以应该使用高效率的二分查找，实在想不出来我就上网搜了一下，发现可以用排序+upper_bound的方法快速实现结果。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<cmath>
#include<iomanip>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
#define PI acos(-1)
int a[100000+5];
int n;
int temp;
bool check(int x)
{int cnt = 0;for(int i=0; i<n; i++){int t=upper_bound(a,a+n,a[i]+x)-a;//比a[i]+x小的元素的个数cnt+=(t-i-1);//排除a[i]之前的那些元素,共有i+1;}if(cnt>=temp) return true;  else return false;
}
int main()
{while(scanf("%d",&n)!=EOF){for(int i=0;i<n;i++)scanf("%d",&a[i]);sort(a,a+n);int m=n*(n-1)/2;temp=(m+1)/2;int l=0,r=a[n-1]-a[0];int ans;while(l<=r)//二分搜索{int mid=(l+r)>>1;if(check(mid))ans=mid,r=mid-1;else l=mid+1;}printf("%dn",ans);}return 0;
}

Description

Inhabitants of the Wonderland have decided to hold a regional programming contest. The Judging Committee has volunteered and has promised to organize the most honest contest ever. It was decided to connect computers for the contestants using a "star" topology - i.e. connect them all to a single central hub. To organize a truly honest contest, the Head of the Judging Committee has decreed to place all contestants evenly around the hub on an equal distance from it. 
To buy network cables, the Judging Committee has contacted a local network solutions provider with a request to sell for them a specified number of cables with equal lengths. The Judging Committee wants the cables to be as long as possible to sit contestants as far from each other as possible. 
The Cable Master of the company was assigned to the task. He knows the length of each cable in the stock up to a centimeter,and he can cut them with a centimeter precision being told the length of the pieces he must cut. However, this time, the length is not known and the Cable Master is completely puzzled. 
You are to help the Cable Master, by writing a program that will determine the maximal possible length of a cable piece that can be cut from the cables in the stock, to get the specified number of pieces.
Input

The first line of the input file contains two integer numb ers N and K, separated by a space. N (1 = N = 10000) is the number of cables in the stock, and K (1 = K = 10000) is the number of requested pieces. The first line is followed by N lines with one number per line, that specify the length of each cable in the stock in meters. All cables are at least 1 meter and at most 100 kilometers in length. All lengths in the input file are written with a centimeter precision, with exactly two digits after a decimal point.
Output

Write to the output file the maximal length (in meters) of the pieces that Cable Master may cut from the cables in the stock to get the requested number of pieces. The number must be written with a centimeter precision, with exactly two digits after a decimal point. 
If it is not possible to cut the requested number of pieces each one being at least one centimeter long, then the output file must contain the single number "0.00" (without quotes).
Sample Input

4 11
8.02
7.43
4.57
5.39
Sample Output

2.00

题意：有n段长度分别为Li的电缆，要求把它们分割成K条长度为X的电缆，问X的最大值为多少。

题解：将X视为变量，可知它的范围为0~max;  那么问题就变成了电缆长度取X时，所得的电缆条数大于，还是等于，或小于K的问题。  用二分查找法能很快的找出K的值，不过要注意精度，直接输出时会四舍五入，五入时的结果肯定是错的，注意向下取整。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<cmath>
#include<iomanip>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define maxn 10010
#define INF 100001
double a[maxn];
int n,k;bool dix(double x)
{int num=0,i;for(i=0;i<n;++i)num+=(int)(a[i]/x);return num>=k;
}int main()
{while(scanf("%d%d",&n,&k)!=EOF){int i;for(i=0;i<n;++i)scanf("%lf",&a[i]);double left=0,right=INF,mid;i=1000;while(i--){mid=(left+right)/2;if(dix(mid))left=mid;elseright=mid;}printf("%0.2fn",floor(right*100)/100);}return 0;
} 

学习感悟

二分是一个很有意思的算法，提供了一个解决问题的另一思路，操作起来的想法也需要变通，有时候会用到其他知识点，这也是需要继续深入钻研学习的一个重要方面。