题解 P1599 【结算日】

LZHlzh · 2016-12-27 12:38:55 · 题解

首先，核心思想是少走回头路（正如有一个题解说的一样），所以需要的是如果能够偿还欠债就立刻回头偿还（如果你继续往下走的话至少需要多走2m的回头路），目测法得显然正确。

代码如下（应该很短了吧）

#include<iostream>
using namespace std;
int n,x,sum,ans,l;
bool flag;
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        sum+=x;//记录当前已经走过的总负债与收回的和
                ans+=1;//向前走一米
        if ((sum>=0)&&flag){flag=0;ans+=(i-l)*2;}//负债小于收回，回去还债
        if ((sum<0)&&!flag){flag=1;l=i;}//记录最先开始负债的位置
    }
    cout<<ans;
}