瓶颈问题
按照我们之前学过的二分答案的套路来看下面的问题（下面的01都是check函数的返回值）：
在一个单调递增的序列中，找到$x$这个数字在哪。
那么我们可以发现，整个问题是0 0 0 0 1 0 0 0 0这种类型的，因为我们的要求是a[i]==x。显然，这种思路是无法进行二分的，这就是所谓的瓶颈问题。
解决瓶颈问题，就是把问题转换一下。比如，上面的例子，我们可以把找$x$转换成找$<=x$的最大的数字，那么问题就变成了1 1 1 1 1 0 0 0这种类型的二分（最大化答案）。把问题转换成找到$>=x$的最小的数字，那么问题就变成了0 0 0 0 0 1 1 1这种类型的二分（最小化答案）。
01分数规划
01分数规划与瓶颈问题
01分数规划就是解决形如：
这个式子的最大值或者最小值问题。$S$是我们选择的数字的集合。
解决这个问题，我们一般假设：
然后二分$mid$的值。可以发现，这种思路下，这是一个瓶颈问题，无法直接二分，所以我们也需要对问题做转换。比如，把问题转换为：
$$\sum_{i\in S} (a_i-mid\cdot b_i)\geq 0$$
或者
$$\sum_{i\in S} (a_i-mid\cdot b_i)\leq 0$$
这样就可以二分了。
check中的贪心策略
我们具体如何选择数字，其实会影响到二分本身的。以【逃避考试】这个题为例。
这个题中，我们要选择$n-k$个数字，使得上面的分式结果最大。
我们可以想到，二分的类型一定是000111或者111000类型的。
例如，我们要求的是：
$$\sum_{i\in S} (a_i-mid\cdot b_i)\geq 0$$
我们能够想到，$mid$越大，那么$a_i-mid\cdot b_i$就越小，如果$mid$很大，那么我们上面的式子是无法成立的，如果$mid$很小，那么上面的式子就有可能成立，可以发现，这样的二分是111000类型（最大化答案）。
我们考虑具体怎么选择。设$c_i=a_i-mid\cdot b_i$。
1、如果我们选择最小的$n-k$个$c_i$，也就是说我们要让这些$c_i$的和尽可能小，也就是让上面的不等式尽可能不成立，这样，二分模型(111000)中的000部分就尽可能大，答案（最后一个$1$）就尽可能小了，并不符合题意。
2、如果我们选择最大的$n-k$个$c_i$，也就是说我们要让这些$c_i$的和尽可能大，也就是让上面的不等式尽可能成立，这样，二分模型(111000)中的111部分就尽可能大，答案（最后一个$1$）就尽可能大，符合题意。
所以，我们选择最大的$n-k$个$c_i$。这个贪心是比较难想的，需要结合二分的01模型来理解。
不过要注意的是，我们的要求还是$\geq 0$，所以最后$return$的时候，要写return ans>=0;
参考代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e3+5;
int n,k,a[N],b[N];
double c[N];
bool check(double mid){
for(int i=1;i<=n;i++){
c[i]=a[i]-mid*b[i];
}
sort(c+1,c+1+n);
double ans=0;
for(int i=k+1;i<=n;i++) ans+=c[i];
return ans>=0;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
double L=0,R=1;
while(R-L>1e-4){//111000型二分
double mid=(L+R)/2.0;
if(check(mid)) L=mid;
else R=mid;
}
printf("%d",int(100*L+0.5));
return 0;
}同样的，我们也可以把这个分式的瓶颈问题转换为：
$$\sum_{i\in S} (a_i-mid\cdot b_i)\leq 0$$
按照同样的逻辑分析一下，$mid$很小的时候，上面的式子无法成立，$mid$很大的时候，上面的式子成立，所以二分类型是000111（最小化答案）。
这个问题中，二分求的是第一个$1$，那么为了让答案最大，那么第一个$1$的位置就要尽可能靠右，也就是让上面的式子尽可能不成立，这样，$0$的数量会多，$1$的数量会少，所以第一个$1$的位置就尽可能靠右了。
按照上面的分析，我们贪心选择的时候，我们要选择最大的$n-k$个$c_i$。可以发现，两种二分的贪心策略是一样的。
参考代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e3+5;
int n,k,a[N],b[N];
double c[N];
bool check(double mid){
for(int i=1;i<=n;i++){
c[i]=a[i]-b[i]*mid;
}
sort(c+1,c+1+n);
double ans=0;
for(int i=k+1;i<=n;i++) ans+=c[i];
return ans<=0;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
double L=0,R=1;
while(R-L>1e-4){//000111型二分
double mid=(L+R)/2.0;
if(check(mid)) R=mid;
else L=mid;
}
printf("%d",int(100*L+0.5));
return 0;
}【徒步】
这个题目中，我们想求的是下列式子最小：
其中，$r_i$是第$i$天走的实际距离，$b_i$是第$i$天所在休息点的愉悦值。
按照套路：
得到一个瓶颈问题。
做法$1$：
$$\sum_{i\in S}(\sqrt{|r_i-len|}-mid\cdot b_i)\geq 0$$
$mid$越大，这个式子越小。可以想到，$mid$很大的时候，这个式子不成立，$mid$很小的时候，这个式子成立。所以二分类型是111000（最大化答案）。
既然我们想要答案最小，那么就是让$1$尽可能少（也就是$0$尽可能多），所以我们选择策略的时候，要使得上面式子尽可能不成立。
而这个过程具体怎么选择，那么就是一个$dp$问题。设$d[i]$代表在$i$这个点休息一次的最小失望值（因为要让上面的式子尽可能不成立，所以选择最小的）。
可以想到，我们计算$dp[i]$的时候，直接去枚举上一个休息点$j$即可。也就是：
$$dp[i]=min_{0\leq j\leq i-1}(dp[j]+\sqrt{|len-(x[i]-x[j])|}-mid\cdot b_i)$$
其中，$dp[j]$是之前休息过程中的最小失望值，$\sqrt{|len-(x[i]-x[j])|}-mid\cdot b_i$是本次休息的失望值。
至于记录休息过程，每次记录一下上一次在哪休息的就可以了，最后从终点$n$开始，一直往回跳，就可以得到答案。
参考代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n,len,x[N],b[N],pre[N],ans[N];
double dp[N];
bool check(double mid){
for(int i=1;i<=n;i++){
dp[i]=1e9;
for(int j=0;j<i;j++){
double t=dp[j]+sqrt(abs(len-(x[i]-x[j])))-mid*b[i];
if(t<dp[i]){
pre[i]=j;
dp[i]=t;
}
}
}
return dp[n]>=0;
}
int main(){
cin>>n>>len;
for(int i=1;i<=n;i++){
cin>>x[i]>>b[i];
}
double l=0,r=1e10;
while(r-l>1e-8){
double mid=(l+r)/2;
if(check(mid)){
l=mid;
}
else r=mid;
}
check(l);//重新跑一边，保证pre数组是正确的
stack<int> st;
int pos=n;
while(pos){
st.push(pos);
pos=pre[pos];
}
while(!st.empty()){
cout<<st.top()<<' ';
st.pop();
}
return 0;
}做法$2$：
$$\sum_{i\in S}(\sqrt{|r_i-len|}-mid\cdot b_i)\leq 0$$
$mid$越大，左侧式子越小。可以想到，$mid$很小的时候，这个式子不成立，$mid$很大的时候，这个式子成立。所以二分类型是000111（最小化答案）。
我们想要答案最小，那么也就是让$1$尽可能地多，也就是说，让上面的式子尽可能成立。
后续过程无需多言，我们尽可能成立，也就是选择尽可能小的，所以$dp$策略依旧不变。
参考代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n,len,x[N],b[N],pre[N],ans[N];
double dp[N];
bool check(double mid){
for(int i=1;i<=n;i++){
dp[i]=1e9;
for(int j=0;j<i;j++){
double t=dp[j]+sqrt(abs(len-(x[i]-x[j])))-mid*b[i];
if(t<dp[i]){
pre[i]=j;
dp[i]=t;
}
}
}
return dp[n]<=0;//这里别忘了改
}
int main(){
cin>>n>>len;
for(int i=1;i<=n;i++){
cin>>x[i]>>b[i];
}
double l=0,r=1e10;
while(r-l>1e-8){
double mid=(l+r)/2;
if(check(mid)){
r=mid;
}
else l=mid;
}
check(l);
stack<int> st;
int pos=n;
while(pos){
st.push(pos);
pos=pre[pos];
}
while(!st.empty()){
cout<<st.top()<<' ';
st.pop();
}
return 0;
}【平均数】
给定一个序列，在序列中选择一个长度大于等于$m$的区间，使得这个区间的平均数最大。
其实对应的式子为：
同理，进行假设和变换（下面$len$指区间长度）：
同理，也有两种做法：
做法1：
$$\sum_{i\in S}(a_i-mid)\geq 0$$
$mid$越大，这个式子越小。可以想到，$mid$很大的时候，这个式子不成立，$mid$很小的时候，这个式子成立。所以二分类型是111000（最大化答案）。
既然我们想要答案最大，那么就是让$1$尽可能多（也就是$0$尽可能少），所以我们选择策略的时候，要使得上面式子尽可能成立。
可以想到，我们要选最大的情况。这个题目说，我们要选择一段连续的区间，那么我们可以使用前缀和进行优化，也就是对$a_i-mid$做前缀和。
我们可以枚举每个$sum[i]$，我们能够想到，$sum[i]-sum[j]$就代表了区间$[j+1,i]$的和。$sum$减谁好呢？我们找最小的$sum[j]$即可。
至于区间长度至少为$m$，我们在枚举$i$的时候，$j$最大到$i-m$即可。因为再往后，区间长度就不够了。
参考代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
double sum[300010],a[300010];
bool check(double mid){//minn找最小的前缀和，maxn找最大的区间和
double minn=0,maxn=-0x3f3f3f3f;
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i]-mid;
if(i>=m){
minn=min(minn,sum[i-m]);
maxn=max(maxn,sum[i]-minn);
}
}//minn初值为0，是因为sum[i]可以减去sum[0]，也就是整个前缀和这个区间
return maxn>=0;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
double L=0,R=20000;
while(R-L>1e-6){
double mid=(L+R)/2.0;
if(check(mid)) L=mid;
else R=mid;
}
printf("%d",int(R*1000));
return 0;
}做法$2$：
$$\sum_{i\in S}(a_i-mid)\leq 0$$
$mid$越大，这个式子越小。可以想到，$mid$很大的时候，这个式子成立，$mid$很小的时候，这个式子不成立。所以二分类型是000111（最小化答案）。
我们想让答案尽可能地大，也就是让$1$尽可能地少，也就是让上面的式子尽可能不成立。所以选择最大的情况（两种做法的策略依旧相同）。
剩下的推导不必多说。
参考代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
double sum[300010],a[300010];
bool check(double mid){
double minn=0,maxn=-0x3f3f3f3f;
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i]-mid;
if(i>=m){
minn=min(minn,sum[i-m]);
maxn=max(maxn,sum[i]-minn);
}
}
return maxn<=0;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
double L=0,R=20000;
while(R-L>1e-6){
double mid=(L+R)/2.0;
if(check(mid)) R=mid;
else L=mid;
}
printf("%d",int(R*1000));
return 0;
}【服务器】
这是本节课最复杂的一个题目了。
本题依旧是求下列式子的一个最小值：
但是，还有$n$个区间$[s_i,t_i]$，要求我们选的时候，必须保证选择的区间能够将$[1,t]$这个区间完全覆盖，不能有漏的情况。这就是这个题的难点了。
我们依旧进行假设和变换：
做法$1$：
$$\sum_{i\in S}(a_i-mid*b_i)\leq 0$$
$mid$越大，这个式子越小。可以想到，$mid$很大的时候，这个式子成立，$mid$很小的时候，这个式子不成立。所以二分类型是000111（最小化答案）。
这个题目要让答案尽可能小，也就是让$1$尽可能多，也就是让上面的式子尽可能成立。所以选择最小的情况即可。
选择的时候，我们想到，如果$c_i=a_i-mid*b_i\leq 0$，那么这个区间我们是必选的（因为是负收益，会让上面那个式子尽可能地小）。$c_i>0$的情况，我们尽可能地少选。
其实看到这里，能够发现这是D4区间贪心这节课，区间覆盖问题的一个变型问题。但是，不同的是，每个区间带上了权值。看似好像能够按照区间贪心的思路来做，但是对于非必选的区间，如何选择才能保证，既能够覆盖整个区间，又能够让答案尽可能小呢？可以发现，有很多种选择，贪心是难以决策的，所以我们需要使用$DP$。
现在要解决的问题是，第$i$个区间带一个权值$c_i$，我们要选择若干个区间，使得$[1,t]$被完全覆盖，并且权值总和尽可能地小。
二分部分省略。思考$check$函数如何实现。为了保证所有的必选区间都能选上，我们可以先把所有的$c\leq 0$的区间选上，然后剩下的区间，我们进行一次$dp$。
这样，$dp[i]$的含义是，覆盖了区间$[1,i]$，权值最小的选择情况。注意，我们$dp$只负责选择非必选的区间，也就是$c>0$的区间。必选区间一开始已经全选了。
我们思考，我们遍历到第$i$个区间的时候，需要和之前的区间连接起来。可以想到，我们选的上一个区间，右端点必须大于等于第$i$个区间的左端点+1，这样才能连接上。所以，我们枚举上一个区间，维护一个最小值$minn$。
我们和上一个区间连接起来了，那么$dp[i]$就要更新为$minn+c_i$。维护最小值即可。
不过这里有一个很容易忽略的小细节：我们遍历到的区间，或许不需要和之前的区间连接起来！因为我们必选的区间可能把整个前缀都已经覆盖了！！这种情况，$minn=0$即可。
注意到，上面的做法，时间复杂度为$O(n^2log_2 n)$，对于本题来说已经足够（课件上的做法），但是这个题是有加强版的（hdu6240），在这个题中，$n$到了$10^5$，所以上面的思路还需要继续优化。
我们注意到，二分的这个$log$是没法省的，$check$中的$O(n)$遍历一遍也是无法省的，那么，另一个$n$哪来的？$dp$的时候，我们枚举上一个区间，这个复杂度是$O(n)$的，这是非常浪费时间的！
实际上，我们可以考虑使用priority_queue。我们把$dp$的信息插入到priority_queue中，每次取最小值即可。注意，这时，$DP$有两个值要考虑：$c_i$的和，以及最远覆盖到的右端点。我们按照$c_i$的和小的优先，建立一个priority_queue。每次取最小值的时候，如果这个区间的右端点小于当前枚举到的区间的左端点+1，那么这个区间就不能选，我们把它弹出。否则，这个区间可以选。这样，我们$O(log_2 n)$的时间复杂度就完成了找最小的$dp$值的过程。
既然使用了priority_queue，那么$dp$数组也可以省略了。具体操作看参考代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,t;
struct node{
int l,r,a,b;
double c;
bool operator<(node x)const{
return l<x.l||l==x.l&&r<x.r;
}
}pt[4005];
struct dpnode{
double value;
int R;
dpnode(double v=0,int r=0){
value=v,R=r;
}
bool operator<(const dpnode& t)const{
if(value==t.value) return R>t.R;
return value>t.value;
}
};
bool check(double x){
priority_queue<dpnode> q;
double sum=0;int maxn=0;
for(int i=1;i<=n;i++){
pt[i].c=pt[i].a-x*pt[i].b;
if(pt[i].c>0) continue;
sum+=pt[i].c;
if(pt[i].l<=maxn+1) maxn=max(maxn,pt[i].r);
}
for(int i=1;i<=n;i++){
double minn=1e9;
while(!q.empty()&&q.top().R<pt[i].l-1) q.pop();
if(!q.empty()) minn=min(minn,q.top().value);
if(maxn>=pt[i].l-1) minn=0;//可以不考虑连接情况
//注意到必选区间不在dp的维护范围内，所以只考虑和之前区间的连接情况
if(pt[i].c<=0) q.push(dpnode(minn,pt[i].r));
else q.push(dpnode(minn+pt[i].c,pt[i].r));
}
while(!q.empty()&&q.top().R<t) q.pop();
return q.top().value+sum<=0;
}
int main(){
scanf("%d%d",&n,&t);
for(int i=1;i<=n;i++) scanf("%d%d%d%d",&pt[i].l,&pt[i].r,&pt[i].a,&pt[i].b);
sort(pt+1,pt+1+n);
double L=0,R=1005;
while(R-L>1e-4){
double mid=(L+R)/2.0;
if(check(mid)) R=mid;
else L=mid;
}
printf("%.3lf\n",R);
return 0;
}做法$2$：
$$\sum_{i\in S}(a_i-mid*b_i)\geq 0$$
$mid$越小，这个式子越大。可以想到，$mid$很小的时候，这个式子成立，$mid$很大的时候，这个式子不成立。所以二分类型是111000（最大化答案）。
这个题目要让答案尽可能小，也就是让$1$尽可能少，也就是让上面的不等式尽可能不成立，所以选择最小的情况，可以发现，这里的策略依旧是和做法$1$相同，只是二分，以及$check$返回的时候的式子不同而已。
参考代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,t;
struct node{
int l,r,a,b;
double c;
bool operator<(node x)const{
return l<x.l||l==x.l&&r<x.r;
}
}pt[4005];
struct dpnode{
double value;
int R;
dpnode(double v=0,int r=0){
value=v,R=r;
}
bool operator<(const dpnode& t)const{
if(value==t.value) return R>t.R;
return value>t.value;
}
};
bool check(double x){
priority_queue<dpnode> q;
double sum=0;int maxn=0;
for(int i=1;i<=n;i++){
pt[i].c=pt[i].a-x*pt[i].b;
if(pt[i].c>0) continue;
sum+=pt[i].c;
if(pt[i].l<=maxn+1) maxn=max(maxn,pt[i].r);
}
for(int i=1;i<=n;i++){
double minn=1e9;
while(!q.empty()&&q.top().R<pt[i].l-1) q.pop();
if(!q.empty()) minn=min(minn,q.top().value);
if(maxn>=pt[i].l-1) minn=0;//可以不考虑连接情况
if(pt[i].c<=0) q.push(dpnode(minn,pt[i].r));
else q.push(dpnode(minn+pt[i].c,pt[i].r));
}
while(!q.empty()&&q.top().R<t) q.pop();
return q.top().value+sum>=0;
}
int main(){
scanf("%d%d",&n,&t);
for(int i=1;i<=n;i++) scanf("%d%d%d%d",&pt[i].l,&pt[i].r,&pt[i].a,&pt[i].b);
sort(pt+1,pt+1+n);
double L=0,R=1005;
while(R-L>1e-4){
double mid=(L+R)/2.0;
if(check(mid)) L=mid;
else R=mid;
}
printf("%.3lf\n",R);
return 0;
}不过要注意的是，这个dp无法使用单调队列进行优化，因为val和R都需要考虑，而不是一味的直接维护单调性。
发表评论