C++程序设计：走格子

淩亂°似流年 2022-12-02 15:20 168阅读 0赞

**【问题描述】**

有编号1~n的n个格子，机器人从1号格子顺序向后走，一直走到n号格子，并需要从n号格子走出去。机器人有一个初始能量，每个格子对应一个整数A\[i\]，表示这个格子的能量值。如果A\[i\] > 0，机器人走到这个格子能够获取A\[i\]个能量，如果A\[i\] < 0，走到这个格子需要消耗相应的能量，如果机器人的能量 < 0，就无法继续前进了。问机器人最少需要有多少初始能量，才能完成整个旅程。

例如：n = 5。\{1，-2，-1，3，4\} 最少需要2个初始能量，才能从1号走到5号格子。途中的能量变化如下3 1 0 3 7。

**【输入形式】**

第1行：1个数n，表示格子的数量。(1 <= n <= 50000)

第2 ~ n + 1行：每行1个数A\[i\]，表示格子里的能量值(-1000000000 <= A\[i\] <= 1000000000)

**【输出形式】**

输出1个数，对应从1走到n最少需要多少初始能量。

**【样例输入】**

5  
1  
\-2  
\-1  
3  
4

**【样例输出】**

2

下面是我大一时写的代码：

#include <iostream>
    using namespace std;
    int main() { 
    	int n,ori,i,energy;
    	bool x;
    	cin>>n;
    	int a[n];
    	for(i=0; i<n; i++)
    		cin>>a[i];
    	for(ori=0; ; ori++) { 
    		energy=ori;
    		x=true;
    		for(i=0; i<n; i++) { 
    			energy+=a[i];
    			if(energy<0) { 
    				x=false;
    				break;
    			}
    		}
    		if(x) { 
    			cout<<ori;
    			return 0;
    		}
    	}
    }

有点蠢了。这道题目其实在问**数组的最小前缀和**。如果该值为x，那么结果就为-x（x<0）或0（x>=0）。累加一遍即可，时间复杂度为O(N)。

发表评论取消回复

表情：

评论列表（有 0 条评论，168人围观）

还没有评论，来说两句吧...

相关阅读

相关走格子

有编号1-n的n个格子，机器人从1号格子顺序向后走，一直走到n号格子，并需要从n号格子走出去。机器人有一个初始能量，每个格子对应一个整数Aii，表示这个格子的能量值。如果Aii

偏执的太偏执、/ 2024年02月18日 22:08/ 0 赞/ 55 阅读

相关（每日一练c++）CC187 走格子

前言 C++是一种计算机高级程序设计语言，由C语言扩展升级而产生，最早于1979年由本贾尼·斯特劳斯特卢普在AT&T贝尔工作室研发。 C++既可以进行C语言的过程化

浅浅的花香味﹌/ 2023年10月04日 18:04/ 0 赞/ 54 阅读

相关机器人走格子

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为1

绝地灬酷狼/ 2023年02月22日 12:17/ 0 赞/ 20 阅读

相关金币馅饼（动态规划走格子）

https://ac.nowcoder.com/acm/problem/25147 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVp

秒速五厘米/ 2023年01月13日 01:46/ 0 赞/ 163 阅读

相关 C++程序设计：走格子

【问题描述】有编号1~n的n个格子，机器人从1号格子顺序向后走，一直走到n号格子，并需要从n号格子走出去。机器人有一个初始能量，每个格子对应一个整数A\[i\]，表示这个格

淩亂°似流年/ 2022年12月02日 15:20/ 0 赞/ 169 阅读

相关走格子

有编号1-n的n个格子，机器人从1号格子顺序向后走，一直走到n号格子，并需要从n号格子走出去。机器人有一个初始能量，每个格子对应一个整数A i i，表示这个格子的能量值。如果A

蔚落/ 2022年06月12日 06:43/ 0 赞/ 198 阅读

相关问题 : 走格子

题目描述有编号1-n的n个格子，机器人从1号格子顺序向后走，一直走到n号格子，并需要从n号格子走出去。机器人有一个初始能量，每个格子对应一个整数A\[i\]，表示这个格子

红太狼/ 2022年06月10日 07:13/ 0 赞/ 235 阅读

相关走格子

【问题描述】有编号1~n的n个格子，机器人从1号格子顺序向后走，一直走到n号格子，并需要从n号格子走出去。机器人有一个初始能量，每个格子对应一个整数A\

Myth丶恋晨/ 2022年06月03日 01:50/ 0 赞/ 236 阅读

相关走格子/棋盘问题

1，给定一个n\n的格子或棋盘，问从左下角走到右上角的走法总数（每次只能向右或向上移动一个方格边长的距离）解答：我们可以把棋盘的左下角看做二维坐标的原点(0,0)，把棋盘的

朱雀/ 2021年11月19日 14:46/ 0 赞/ 325 阅读

相关 C++程序设计

C++程序设计　　之前学过C++课程，但是时间有点久，忘了很多，这里做一个简单的回顾。　　网站推荐： [C++在线编译器][C] 　　学习C++之前，您可以先了解[C

布满荆棘的人生/ 2021年10月01日 03:40/ 0 赞/ 493 阅读