【超绝USACO】贪心还是模拟？

注意：本笔记来自上课速记，看不懂也别看了
——————————————————————————————————————
问题1：如何思考？！？！！？？！？
不能拿到钱第一时间回去还：WA数据
e.g 100 -200 -200 250 -200 300
多走了1步(15>14)
所以走完所有的步数再回来还钱

问题2：如何判定什么时候回头？！？！？！？！？
贪心：
为什么？求最少步数
最多答案是3n（第一个欠钱非常多） 最少答案1n（直接走到尾） 所以范围是1n~3n
最少路径：走到尾再回头还钱再去终点（最多3n）

答疑：
为什么不用二分？1<=n<=1000000
为什么不能拿到钱第一时间回去还？不能保证第一个欠钱的地方之后没有欠钱的地方
为什么不两种都走一遍？1<=n<=1000000
*/

——————————————————————————————————————
代码鉴赏部分：

CODE1：刁老师版本

#include<iostream>
#include<queue>
using namespace std;
int a[1000100];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    long long sum=0,ans=0,ax=0,axId;// axID：前面欠的钱的最小下标
    for(int i=0;i<n;i++){
        // 两种情况讨论
		if(a[i]>0){//（正值）
            sum+=a[i];
            if(sum>=-ax && ax){// 是否能把欠的钱都还了（从当前格到下标格）
            	ans+=(i-axId)*2;// 一定是走两趟
                sum+=ax;
                ax=0;// 没有欠债
                axId=i;// 相应更改下标
            }
        }else if(a[i]<0){//（负值）
            if(ax){// 判断：我前面是否欠钱？如果前面没有欠钱，这将会成为一个新的点
                ax+=a[i];
            }else{
                if(sum>=-a[i]){// 能否把钱还掉
                    sum+=a[i];
                }else{
                    ax=a[i];
                    axId=i; //还不掉，记录下标，债务，标记欠债
                }
            }
        }
        ans++;
    }
    cout<<ans;
    return 0;
}

CODE2： AC草精简版本

#include<iostream>
using namespace std;
int n,x,sum,ans,l;
bool flag;
int main(){
    int n;
    cin>>n;
    int sum=0,ans=0,k=0;
    bool f=0;
    for (int i=1;i<=n;i++){
        int x;
        cin >> x;
        sum+=x;//不管正的负的都加一下
        ans++;
        if((sum>=0)&&flag){// 前面有负过
            flag=0;
            ans+=(i-l)*2;// 跑到前面的点来回一趟
        }
        if((sum<0)&&!flag){flag=1;l=i;}
    }
    cout<<ans;
}

——————————————————————————————

真可谓是：超绝USACO，脑力大风暴！