AcWing 431. 守望者的逃离
原题链接
简单
作者:
Air1222
,
2024-04-05 16:56:05
,
所有人可见
,
阅读 3
//因为恢复+瞬移一定比走快,因此只有最后一段是需要走的(距离太短,来不及恢复)
//f[i]表示第i秒走的最远距离,本题状态就一个时间
//用插缝法找最后一段时间,前面瞬移,后面再瞬移的基础上跑,找到最先跑到终点的点
#include <iostream>
using namespace std;
const int N = 300010;
int f[N];
int main()
{
int m,s,t;
cin>>m>>s>>t;
for(int i=1;i<=t;i++)
{
if(m>=10)
{
m-=10;
f[i]=f[i-1]+60;
}
else
{
m+=4;
f[i]=f[i-1];
}
}
for(int i=1;i<=t;i++) f[i]=max(f[i],f[i-1]+17);
for(int i=1;i<=t;i++)
{
if(f[i]>=s)
{
cout<<"Yes"<<endl<<i;
return 0;
}
}
cout<<"No"<<endl<<f[t];
return 0;
}
用于解决,一个方法一定比当前方法优秀,但来不及恢复,找最后恢复点