二分法习题报告（二）
1.寻找段落
链接: 寻找段落.
解题思路：
一个标准的二分模板题。check函数不会写。
题解：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#define maxn 100010
using namespace std
;
int n
, s
, t
, i
;
double l
, r
, mid
, ans
;
double a
[maxn
];
int b
[maxn
];
double sum
[maxn
];
int q
[maxn
];
bool check(double x
) {
int i
, l
= 1, r
= 0;
for (i
= 1; i
<= n
; i
++)
a
[i
] = (double)b
[i
] - x
;
sum
[0] = 0;
for (i
= 1; i
<= n
; i
++)
sum
[i
] = sum
[i
- 1] + a
[i
];
for (i
= 1; i
<= n
; i
++) {
if (i
>= s
) {
while (r
>= l
&& sum
[i
- s
] < sum
[q
[r
]]) r
--;
q
[++r
] = i
- s
;
}
if (l
<= r
&& q
[l
] < i
- t
) l
++;
if (l
<= r
&& sum
[i
] - sum
[q
[l
]] >= 0) return true;
}
return false;
}
int main() {
scanf("%d", &n
);
scanf("%d%d", &s
, &t
);
for (i
= 1; i
<= n
; i
++)
scanf("%d", &b
[i
]);
ans
= l
= -10000; r
= 10000;
while (r
- l
> 1e-5) {
mid
= (l
+ r
) / 2;
if (check(mid
))
ans
= l
= mid
;
else r
= mid
;
}
printf("%.3lf\n", ans
);
return 0;
}
总结：
check中主要用到了两个知识点：
前缀和：前缀和序列比较好理解sum[i]表示a[i]前i个元素的和。单调队列：这个地方看来半天没看懂。。。
2.小车问题
链接: 小车问题.
解题思路
解题思路有两种，第一种比较快的是数学发，直接列出方程解出结果。第二种是二分法，主要说一下二分法。 二分的内容是总长的S，为了找到一个点C（起始点是A，终点是B）。车先送第一个人（p1）到C点，然后车返回，p1自己走到B点。车返回后与另一个人（p2）相遇，带p2到B点。当p1和p2同时到达B点时，时间最短。（这就是check的条件。）
题解
#include<iostream>
#include<math.h>
#include <iomanip>
using namespace std
;
int main()
{
double s
,s1
,s2
,v1
,v2
,t1
,t2
,p
;
double a
,b
;
cin
>>s
>>v1
>>v2
;
s1
=0;
s2
=s
;
do
{
p
=s1
+(s2
-s1
)/2.0;
a
=p
/v2
;
b
=(p
-a
*v1
)/(v1
+v2
);
t1
=a
+(s
-p
)/v1
;
t2
=a
+b
+(s
-(a
+b
)*v1
)/v2
;
if(t1
<t2
)
s2
=p
;
else
s1
=p
;
}
while(fabs(t1
-t2
)>1e-8);
cout
<<fixed
<<setprecision(6);
cout
<<t1
;
return 0;
}
总结
这可能时做到现在最简单的一题了。主要还是要想好二分要分啥，check函数怎么判断。这是二分法的关键。
3.借教室
链接: 借教室.
解题思路
首先，要明白如为什么要用区间差分而不是区间前缀和：因为这个题每次操作针对的对象都是原本题目中给的元数据，而不是让求某个关系，所以采用差分。
其次，要知道差分会起到怎样的作用：因为diff数组决定着每个元数据的变化大小、趋势，所以，当我们想要针对区间操作时，钱可以转化成对diff数组操作：
diff[l[i]]+=d[i]; diff[r[i]+1]-=d[i];//d[i]是指每天要借的教室数
因为后面的元数据都由之前的diff数组推导出来，所以改变diff[i]就相当于改变i之后的每一个值，并通过重新减去改变的量，达到操作区间的目的。
then，我们需要想明白策略：从第一份订单开始枚举，直到无法满足或者全枚举完结束。
最后，一点提示，我下面的标程是通过比大小来判断是否满足，而不是作差判负数————能不出负数就别出负数，否则容易基佬紫（re）/手动滑稽
题解
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std
;
int n
,m
;
int diff
[1000011],need
[1000011],rest
[1000011],r
[1000011],l
[1000011],d
[1000011];
bool isok(int x
)
{
memset(diff
,0,sizeof(diff
));
for(int i
=1;i
<=x
;i
++)
{
diff
[l
[i
]]+=d
[i
];
diff
[r
[i
]+1]-=d
[i
];
}
for(int i
=1;i
<=n
;i
++)
{
need
[i
]=need
[i
-1]+diff
[i
];
if(need
[i
]>rest
[i
])return 0;
}
return 1;
}
int main()
{
scanf("%d%d",&n
,&m
);
for(int i
=1;i
<=n
;i
++)scanf("%d",&rest
[i
]);
for(int i
=1;i
<=m
;i
++)scanf("%d%d%d",&d
[i
],&l
[i
],&r
[i
]);
int begin
=1,end
=m
;
if(isok(m
)){cout
<<"0";return 0;}
while(begin
<end
)
{
int mid
=(begin
+end
)/2;
if(isok(mid
))begin
=mid
+1;
else end
=mid
;
}
cout
<<"-1"<<endl
<<begin
;
}
总结
一般来说，二分是个很有用的优化途径，因为这样会直接导致减半运算，而对于能否二分，有一个界定标准：状态的决策过程或者序列是否满足单调性或者可以局部舍弃性。（这一点好像之前都没想到） 而在这个题里，因为如果前一份订单都不满足，那么之后的所有订单都不用继续考虑；而如果后一份订单都满足，那么之前的所有订单一定都可以满足，符合局部舍弃性，所以可以二分订单数量。
