牛牛的旅行

NC21580. 牛牛的旅行

描述

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

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

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

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

输入描述

第一行输入一个整数n (1 ≤ n ≤ 300)

第二行输入n个元素pos[i]( 1 ≤ pos[i] ≤ 10⁵), 表示每个人的位置

第三行输入n个元素delta[i](-10⁵ ≤ delta[i] ≤ 10⁵)表示每个人的需求


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

输出描述

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

示例1

输入:

5
3 14 15 92 101
-3 2 3 -3 1

输出:

说明:

总共5个人，0号人在3位置，需要3的购买量. 1号人在14位置有2的供应量. 2号人在15位置有3的供应量. 3号人在92位置有3的购买量。4号人在101位置有1的供应量，最优路线如下
第一步走到15位置. 买下2号人所有的供应量
第二步走到14位置，买下1号人所有的供应量，当前alice一共有5个单位的量。
第三步走到3位置，卖出3个单位。还剩2个单位
第四步走到101，买下4号人的供应量，当前手里一共有3个单位
第五步走到92，卖给3号人3个单位
最后走到101结束旅程
一共花的时间是 15+1+11+98+9+9 = 143.

示例2

输入:

8
1 2 4 8 16 32 64 128
-1 -1 -1 -1 1 1 1 1

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 500K, 提交时间: 2023-07-18 14:08:46

#include<bits/stdc++.h>
using namespace std;
int a[305],b[305],n,l,sum,ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++){
        if(sum>=0&&sum+b[i]<0)l=a[i];
        if(sum<0&&sum+b[i]>=0)ans+=(a[i]-l)<<1;
        ans+=a[i]-a[i-1];
        sum+=b[i];
    }
    cout<<ans<<endl;
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 452K, 提交时间: 2022-07-10 16:42:18

#include<bits/stdc++.h>
using namespace std;
int n,m,l,w,a[301],d[301];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	for(int i=1;i<=n;i++)
	cin>>d[i];
	for(int i=1;i<=n;i++)
	{
		if(w<0&&w+d[i]>=0)
		 m+=(a[i]-l)*2;
		if(w>=0&&w+d[i]<0)
		 l=a[i];
		m+=a[i]-a[i-1];
		w+=d[i];
	}
	cout<<m;
	return 0;
}

Python3 解法, 执行用时: 42ms, 内存消耗: 4600K, 提交时间: 2022-11-08 21:47:15

n=int(input())
pos=list(map(int,input().split()))
delta=list(map(int,input().split()))
sum=pos[n-1]
tem=0
deltasum=0
for i in range(len(delta)):
    deltasum+=delta[i]
    if deltasum>=0:
        sum=sum+2*(pos[i]-pos[tem])
        tem=i+1
print(sum)