题目传送门
题目描述：
给出一个1*n的网格。每个格子中可能有人或食物，也可能为空。 人移动一单位距离需要一秒，当移动到一个含有食物的格子时他就会把食 物吃掉。吃不需要花费时间。人可以任意地变动行进方向且不花费时间。 你的任务是计算出所有食物被人吃完的最少时间。 //注：所有人可以一起移动，且
n
≤
1
e
5
n\leq 1e5
n≤1e5
Solution
看到这道题的范围，就知道这道题基本只能用
n
l
o
g
n
nlogn
nlogn的算法过（当然如果你收
n
n
n\sqrt n
nn
我也没话说） 想到
l
o
g
log
log,我们就想到了二分答案
没错，这道题就是二分答案。
我们二分最少的时间开一个数组来记录每一个包装向右离的最近的人的那个位置，这个可以预处理出来我们分情况讨论 1、如果当前的字符是P，直接把他右边mid个单位的包装吃掉 2、如果当前的字符是*，再根据人的走向分情况讨论： 设他离人的最近距离为d，那么分两种情况： i、先左后右，如下图： 这是重叠部分就位d ii、先右后左，如下图：
这时重叠部分就是
m
i
d
−
d
2
\frac {mid-d} 2
2mid−d
为了是路程利益最大化，我们就要比较两者的大小。若前者小于后者，就是先左后右，否则就是先右后左解方程即可
Code
#include<bits/stdc++.h>
using namespace std
;
int n
;
char s
[1010100],ss
[1010100];
int a
[1010100] , len
=0;
int minn
[1010100];
bool check(int x
){
int maxw
=0;
for (int i
=1;i
<=n
;i
++) ss
[i
] = s
[i
];
for (int i
=1;i
<=n
;i
++){
if (ss
[i
] == '.') continue;
if (ss
[i
] == 'P') {maxw
= max(maxw
,i
+x
);continue;}
if (ss
[i
] == '*'){
if (i
<=maxw
) continue;
int d
= minn
[i
] - i
;
if (d
<0 || d
>x
) return 0;
if (3*d
<= x
) maxw
= max(maxw
,minn
[i
]+x
-d
-d
);
else maxw
= max(maxw
,minn
[i
]+(x
-d
)/2);
ss
[minn
[i
]] = '.';
}
}
return 1;
}
int main(){
cin
>>n
>>s
+1;
for (int i
=1;i
<=n
;i
++){
if (s
[i
] == '*') a
[++len
] = i
;
if (s
[i
] == 'P') {
for (int j
=1;j
<=len
;j
++) minn
[a
[j
]] = i
;
len
= 0;
}
}
int l
=0,r
=1e9;
while (l
+1<r
){
int mid
= l
+r
>>1;
if (check(mid
)) r
=mid
;else l
=mid
;
}
printf("%d",check(l
)?l
:r
);
return 0;
}
