学习时间与内容
- 8：30-8：40起床打卡
- 9：00-11：30回顾昨天的知识点、复习希尔排序
- 14：00-18：00 学习二分、刷题
-
晚上整合总结
1.希尔排序
因为我们之前学过的插入排序法在小规模数据或者数据基本有序时十分高效，所以希尔排序就在这基础上进行了优化改动，它将数据进行了分组，将较大的数据集合分割成了若干个小组，然后对每一个小组分别进行插入排序。
它新增了一个增量，一开始增量为n/2，然后增量不断减少，当增量减少到1，整个数组的元素就分为了一组时就相当于一个插入排序。
由于希尔排序在插入时是跳跃插入的，可能会破坏它的稳定性，所以希尔排序不稳定。
时间复杂度O(nlogn)
希尔排序模板：
for(int d=n/2;d>0;d/=2)//shell排序增量
{
for(int p=d;p<n;p++)//插入排序模板
{
tmp=a[p];
for(i=p;i>=d&&a[i-d]>tmp;i-=d)
a[i]=a[i-d];
a[i]=tmp;
}
}
2.二分样例
http://www.jsuacm.cn/problem.php?cid=1618&pid=2
在我农场上有N头牛（1<=N<=50000），我想出了一个杂技特技：站到彼此上面，形成一个有一定高度的垂直堆叠，我就让这些牛来练习这个杂技,牛正在试图弄清楚它们应该在这堆奶牛中排列的顺序。每头N头牛具有相关的体重(1<=W_i<=10000)和强度(1<=S_i<=1000000000)。一头牛倒下的风险等于它身上所有牛的总体重（当然不包括它自己的体重）减去它的强度（这样一来，一头更强壮的牛的风险就更低）。你的任务是确定牛的顺序，使任何一头牛的最大风险最小化。
格式
输入格式
第1行：整数N为单行。
行2…N+1：行i+1用两个空分整数W和S描述牛。
输出格式
一个单一的整数，给出所有奶牛的最大风险，在任何优化排序，使风险最小化。
这道题的难点主要是搞清怎样能使得风险最小化，每头牛都有一个体重和一个强度，风险的值为这头牛以上不包括它本身的体重减去它的强度。如果只对强度和体重或者他们的比值进行排序都不可能达到最大风险的最小化。
所以可以这样理解，强度越大它能够承受的体重也就越大，所以强度越大就越放在下面来承受更大的体重。体重越大就需要强度越大的牛来承受它，所以为了避免这种情况，我们也把体重越大的放在下面，以免压垮下面的牛。
所以我们应该对体重和强度的和来进行排序，越大的越在下面。排好序就可以来一个前缀和扫一遍，用前缀和的体重减去这头牛的体重，因为是求奶牛的最大风险，所以我们比较最终保留一个风险最大值。
这里还有一个值得注意的地方最上面那头牛（第一头牛）也要用它前缀和体重减去它的强度（虽然第一头牛的前缀和体重为0）风险值为负。因为整体最大风险的值也可能是负数，假设第i头牛的前缀和体重减去它的强度即为：sum—S<0假设为 4-7=-3，而第一头牛的前缀和体重为0（因为它上面没牛嘛），强度为2那么它的风险为-2，我们找的是最大风险值，很明显-2>-3所以，第一头牛的风险值更大一点。因此，我们必须从最上面那头牛（也就是第一头牛)开始循环。这也是我WA好几次，我改了下值发现的。
下面看下我的AC代码：
#include <stdio.h>
struct node
{
int w,s,v;
int sum;
};
struct node a[50000+10];
int n;
void sort(int left,int right)
{
int i,j;
struct node temp,t;
if(left>right)
return;
temp=a[left];
i=left;
j=right;
while(i!=j)
{
while(a[j].sum>=temp.sum&&i<j)
j--;
while(a[i].sum<=temp.sum&&i<j)
i++;
if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
a[left]=a[i];
a[i]=temp;
sort(left,i-1);
sort(i+1,right);
}
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int i,j,ans=-99999999;
scanf("%d",&n);
for(i=0;i<n;i++)
{scanf("%d%d",&a[i].w,&a[i].s);
a[i].sum=a[i].w+a[i].s;//对体重和强度排序，所有要累加
a[i].v=0;//对每个前缀和的累加器赋初值
}
sort(0,n-1);//用个快排，以免数据过大会时间超限
for(i=1;i<n;i++)//这里是前缀和所以从第二头牛开始
a[i].v=a[i-1].w+a[i-1].v;//前缀和，对上面的牛的体重累加
for(i=0;i<n;i++)//第一头牛也要算风险值，即便这个风险值为负数
ans=max(ans,a[i].v-a[i].s);//找到最大的风险值
printf("%d",ans);
}
问题 A: 切绳子
描述
有n条绳子，长度分别为L[i]。如果从他们中切割出k条长度相同的绳子的话，这k条绳子每条最长能有多长？（答案保留小数点后两位（直接舍掉两位后的小数），规定1单位长度的绳子最多可以切割成100份）
格式
输入格式
包含多组输入
输入n,k,（1<=n,k<=10000）
然后n行，输入L[i],代表每一条绳子的长度(1<=L[i]<=100000)
输出格式
切出k条长度相等的绳子最大长度是多少，输出保留两位小数
样例
样例输入 Copy
4 11
8.02
7.43
4.57
5.39
样例输出 Copy
2.00
这里如果直接原样输入结果就会出错。题目要求保留两位小数，后面的可以舍去，也就是说最多能够影响到结果的是第三位小数（第三位进位），在二分mid的时候（left+right）/2的时候看是否能进位，所以我们可以直接先将每个数据扩大一百倍。接下来就是求最大值的情况，就也是让绳子数目尽量少，求绳子数目就让每根绳子除以二分的mid然后将绳子数相加跟k进行比较。在这里二分区间可以用[0,最长的绳子长度】右区间不选最短绳子是因为当绳子有多条，但K=1的时候绳子最长的情况就是可以不用切绳子，就是最长的那跟绳子。
下面看AC代码
#include <stdio.h>
double a[10000+10];
int n,m;
void sort(int left,int right)
{
int i,j;
double t,temp;
if(left>right)
return;
temp=a[left];
i=left;
j=right;
while(i!=j)
{
while(a[j]>=temp&&i<j)
j--;
while(a[i]<=temp&&i<j)
i++;
if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
a[left]=a[i];
a[i]=temp;
sort(left,i-1);
sort(i+1,right);
}
int check(int mid)
{
int i,j,ans=0;
for(i=0; i<n; i++)
ans+=a[i]/mid;
if(ans>=m)//段数大于m说明绳子不够长，相等的话也可以试着在ans==m时查找是否还有更长点的绳子
return 1;
else
return 0;
}
int main()
{
int i,j;
int l,r,mid;double ans;
while(~scanf("%d%d",&n,&m))
{
for(i=0; i<n; i++)
{
scanf("%lf",&a[i]);
a[i]*=100;
}
sort(0,n-1);//用快排以防超时
/* for(i=0; i<n; i++)
printf("%.2lf ",a[i]);*/
l=0;
r=a[n-1];//二分区间是【0，最长的绳子长度】
while(l<=r)
{
mid=(l+r)/2;
if(check(mid))//检查mid是否合法
{
l=mid+1;//合法就扩张左区间来寻求更大一点的值
ans=mid;//暂时记录当前查找到的最大值
}
else
r=mid-1;
}
ans/=100;//最后还原数据
printf("%.2lf\n",ans);
}
}
问题 B: 如何放牛
描述
农夫有n个牛栏，m头牛，然后要让你把m个牛都放进牛栏里，让两头牛之前的最大的最小距离
格式
输入格式
多组输入
输入n,m (1<=m<=n<=100000)
下面n行是牛栏的位置xi (0 <= xi <= 1,000,000,000)
输出格式
输出两头牛最大的最小距离
样例
样例输入 Copy
5 3
1
2
8
4
9
样例输出 Copy
3
FJ可以将他的3头奶牛放在位置1,4和8的摊位上，最小距离为3.
提取主干，查找最大值中的最小值
区间为【0，最大的那个值】，用每次的二分Mid来和两个牛栏之间的距离进行比较，如果Mid比两个牛栏小就说明可以放进去一头牛，ans++,然后对第二个牛栏和第三个牛栏的距离与mid进行比较，看能否放入一头牛，如果放不进去就要用第二个牛栏和第四个牛栏进行比较。最后用放入的牛数ans与m进行比较，因为是查找最小值，所放入的牛ans<m时就说明二分的mid太大了，所以要在mid左边再来二分一个更小的值。
#include <stdio.h>
int a[100000+10],n,m;
void sort(int left,int right)
{
int i,j,t,temp;
if(left>right)
return;
temp=a[left];
i=left;
j=right;
while(i!=j)
{
while(a[j]>=temp&&i<j)
j--;
while(a[i]<=temp&&i<j)
i++;
if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
a[left]=a[i];
a[i]=temp;
sort(left,i-1);
sort(i+1,right);
}
int check(int mid)
{
int i,j,ans=1,t=a[0];
for(i=1; i<n; i++)
{
if(mid<=a[i]-t)//如果二分的mid小于等于两牛栏的距离就说明放的下一头牛
{
ans++;//牛数加一
t=a[i];//记录一下前一个牛栏
}
}
if(ans<m)//如果放入的牛数小于预期的m就说明二分的mid太大难以放入m头牛
return 1;
else
return 0;//说明放入的牛数大于等于m，说明mid太小或者刚刚符合
}
int main()
{
int i,j,mid,ans;
while(~scanf("%d%d",&n,&m))
{
for(i=0; i<n; i++)
scanf("%d",&a[i]);
sort(0,n-1);
i=0;
j=a[n-1];
while(i<=j)
{
mid=(i+j)/2;
if(check(mid))
{
j=mid-1;//因为二分的mid太大所以，区间调整到Mid左边
}
else
{
i=mid+1;//因为Mid太小所以调整区间到mid右边
ans=mid;//同时记录mid的值
}
}
printf("%d\n",ans);
}
}