题解 | #牛牛的旅行#

有n个人在x轴上，每个人的坐标是一个整数，牛牛是一个旅行商人，他在轴上穿梭并与这n个人交易，交易的商品只有一种，每一个人都有对这种商品的需求或者供应，如果delta[i] 是正数，表示这个人要供应delta[i]的数量，如果是负数，表示这个人需要−delta[i]的购买量，保证delta的和非负，一开始牛牛在0位置，手里没有任何商品，每一秒他可以往左或者往右走1个单位的距离，如果他和一个人在同一个位置，就可以与之交易，交易是瞬间发生的，每笔交易的数量是由牛牛决定的，当然他不能卖出超出自己手里含有的商品数量，行走过程中牛牛手里可以拿着任意多的商品，到了一个人的位置，也可以选择不与之交易，最终牛牛需要满足以下两点

1:牛牛必须满足所有人的需求

2:旅行必须要在最后一个人的位置结束。

求最少需要花费多少时间。

第一行输入一个整数n (1 ≤ n ≤ 300)
第二行输入n个元素pos[i]( 1 ≤ pos[i] ≤ 105), 表示每个人的位置
第三行输入n个元素delta[i](-105 ≤ delta[i] ≤ 105)表示每个人的需求

保证pos单调递增，delta的和非负

输出一个整数表示最少需要花费的时间

思路：由于牛牛最后一定是要走到终点的，所以不妨先将在距离的数据输入完毕后，将最终结果的值初始化成最后一个距离数据（在下面代码里为ans=pos[n-1].p）。

用变量anst（初始化为0）来存储牛牛身上的商品数量，post来存储牛牛已经解决的需求的从最小位置开始的连续序列的最大下标（不知道怎么表述最贴切qwq）。

如果anst加上某个值之后<0了，那么表明需求不够，无法解决当前的需求，此时post停止增加，但anst仍然继续累加，直到出现ans>=0,此时表明可以解决前面的需求不够，那么需要走回去再走回来，总路程即为2*(pos[i].p-pos[post].p);

同时因为前面的需求全部解决，所以post=i+1;

这样一直遍历到最后，就可以算出总最小距离。

这个题目最好画图模拟一下，更加直观。

代码如下：

#include<stdio.h>
struct ss{
    int p,nd;
}pos[320];
int main(){
    int n,i,anst=0,post=0,ans=0;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&pos[i].p);
    }
    ans=pos[n-1].p;
    for(i=0;i<n;i++){
        scanf("%d",&pos[i].nd);
        anst+=pos[i].nd;
        if(anst>=0){
            ans+=2*(pos[i].p-pos[post].p);
            post=i+1;
        }//核心代码
    }
    printf("%d\n",ans);
    return 0;
}