1344 走格子

基准时间限制：1 秒

空间限制：131072 KB

分值: 5

难度：1级算法题

　　有编号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。

Input

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

Output

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

输入：

5

1

-2

-1

3

4

输出：

　　　　　2

代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int INF=2147483647UL;
 4 int inf=-2147483648UL; 
 5 int main(){
 6     __int64 n,m,t,minn=INF;
 7     while(scanf("%I64d",&n)!=EOF){
 8         __int64 ans=0;
 9         while(n--){
10             scanf("%I64d",&m);
11             ans+=m;
12             if(ans<0){
13                 minn=min(ans,minn);
14             }
15         }
16         printf("%I64d",-minn);
17     }
18     return 0;
19 }

　　long 和 int 范围是[-2^31,2^31)，即-2147483648~2147483647。而unsigned范围是[0,2^32)，即0~4294967295。即常规的32位整数只能够处理40亿以下的数。

　　当遇到大于40亿的数据，就需要用到C++的64位扩展，即__int64。

　　__int64与unsigned __int64的范围分别是[-2^63, 2^63)与[0,2^64)。即-9223372036854775808~9223372036854775807与0~18446744073709551615(约1800亿亿)。

　　当进行64位与32位的混合运算时，32位整数会被隐式转换成64位整数。但是，VC的输入输出与__int64的兼容就不是很好。

　　一般输入输出是用“%lld”。而如果你使用的是Dev-C++的g++编译器，它使用的是"%I64d"而非"%lld"。

　　用Dev-C++的g++编译器，也会出现警告：

　　[Warning] this decimal constant is unsigned only in ISO C90

　　找到了三种解决方法：

在常数后面增加一个UL标识，或者ULL表示，如2147483647UL，这样就不会报警了
使用十六进制的数字，如0xFFFFFFFF
使用gcc -std=c99 用99标准来编译

　　根据C的标准，出现这个告警，其实也是gcc提醒你该升级你的编译选项了。不过最安全的还是使用十六进制，或者加上UL或者ULL这样的说明。