【题解】跳房子
题目链接
解题思路
这题挺有意思的,看一看是可以在 20 分钟内想到解法,但是在实现的过程中会遇到很多阻碍。
乍一看题面,问的是“至少”,那可以判断出这题大概率是道二分答案题。然后看子任务,在二分的答案下找到最优解,这个就贪心或者 DP。想了会儿贪心不可行就去推 DP 了。
这题 DP 也很好推,就是 $dp[i]=dp[j]+s[i]$ ,其中 j 能够跳到 i。
但是很明显这样做是 $O(n^2logn)$ 的。所以我们要引进单调队列优化。(这之前我一直以为单调队列优化是优先队列优化,于是 TLE 了好几回)
我们不难发现,在对于 i 的可选决策中,有一些实可以延续到 j 的。而如果离 i 近的比离 i 远的 DP[j]大,那肯定选 DP[j],因为远的那个点又远又小,没有竞争力。
单调队列优化就此解决,但是我们发现它不是从 0 - y 都能跳,而是从 x - y 能跳。所以我们需要一个数组保存从 0 - x 的待选决策。
这样这道题就结束了
代码
#include<bits/stdc++.h>
using namespace std;
const long long inf=1e16;
long long dp[500005];
int x[500005];
int s[500005];
struct kkk{
int pos;
long long sum;
};
deque<kkk> q;
kkk dai[5000005];
int dl=1,dr=0;
int n,d,k;
bool check(long long mid){//要用两个priority_queue存储待存区间和可用区间
int addmin,addmax;
if(mid<d){
addmin=d-mid;
addmax=d+mid;
}else{
addmin=1;
addmax=d+mid;
}
while(!q.empty())q.pop_back();
dl=1,dr=0;
for(int i=1;i<=n;i++)dp[i]=-inf;
kkk now,nxt;
for(int i=1;i<=n;i++){
long long ans=-inf;
while(dl<=dr&&dai[dl].pos<=x[i]-addmin){
if(dai[dl].pos<x[i]-addmax){//再也取不到了
dl++;
}else{
while(!q.empty()){
if(q.back().sum<=dai[dl].sum)q.pop_back();
else break;
}
q.push_back(dai[dl]);//可用
dl++;
}
}
while(!q.empty()){//太远了,之后也不可能跳到
if(q.front().pos<x[i]-addmax){//再也取不到
q.pop_front();
}else if(!q.empty()){
ans=max(ans,q.front().sum);//可取,直接用
break;
}
}
dp[i]=ans+s[i];
if(x[i]>=addmin&&x[i]<=addmax)dp[i]=max(dp[i],(long long)s[i]);
nxt.pos=x[i];
nxt.sum=dp[i];
dai[++dr]=nxt;
}
long long maxn=-inf;
for(int i=1;i<=n;i++){
maxn=max(maxn,dp[i]);
}
if(maxn>=k)return 1;
return 0;
}
int main(){
scanf("%d%d%d",&n,&d,&k);
for(int i=1;i<=n;i++){
scanf("%d%d",&x[i],&s[i]);
}
long long l=0,r=1e9+7,mid;
long long ans=-1;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)){
r=mid-1;
ans=mid;
}else{
l=mid+1;
}
}
printf("%d",ans);
return 0;
}