AcWing 730. 機器人跳躍問題
機器人正在玩一個古老的基于DOS的游戲，
游戲中有N+1座建筑——從0到N編號，從左到右排列，
編號為0的建筑高度為0個單位，編號為 i 的建筑高度為H(i)個單位，
起初，機器人在編號為0的建筑處，
每一步，它跳到下一個（右邊）建筑，
假設機器人在第k個建筑，且它現在的能量值是E，下一步它將跳到第k+1個建筑，
如果H(k+1)>E，那么機器人就失去H(k+1)-E的能量值，否則它將得到E-H(k+1)的能量值，
游戲目標是到達第N個建筑，在這個程序中能量值不能為負數個單位，
現在的問題是機器人至少以多少能量值開始游戲，才可以保證成功完成游戲？
輸入格式
第一行輸入整數N，
第二行是N個空格分隔的整數，H(1),H(2),…,H(N)代表建筑物的高度，
輸出格式
輸出一個整數，表示所需的最少單位的初始能量值上取整后的結果，
資料范圍
1≤N,H(i)≤105,
輸入樣例1：
5
3 4 3 2 4
輸出樣例1：
4
輸入樣例2：
3
4 4 4
輸出樣例2：
4
輸入樣例3：
3
1 6 4
輸出樣例3：
3
這道題還是比較簡單的，我觀察到這好像是一個遞增序列，二分法就直接解決了，我寫了第一代版本，
#include<iostream>
using namespace std;
const int N=1e5+10,Mod=1e9+7;
int h[N];
int n;
bool check(int m)
{
long long mid=m;
for(int i=1;i<=n;i++)
{
if(h[i]>mid)
mid-=h[i]-mid;
else
mid+=mid-h[i];
mid%=Mod;
if(mid<0)
return false;
}
return true;
}
int main(void)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&h[i]);
int l=0,r=1e5;
while(l<r)
{
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l;
}
這個測驗樣例沒過，我仔細觀察了一下，原來是爆int了于是我改進了一下check函式，
#include<iostream>
using namespace std;
const int N=1e5+10,Mod=1e9+7;
int h[N];
int n;
bool check(int m)
{
long long mid=m;
for(int i=1;i<=n;i++)
{
if(h[i]>mid)
mid-=h[i]-mid;
else
mid+=mid-h[i];
if(mid>1e5+10)
return true;
else if(mid<0)
return false;
}
return true;
}
int main(void)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&h[i]);
int l=0,r=1e5;
while(l<r)
{
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l;
}
成功AC
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/263919.html
標籤：其他
下一篇：Bits