1344?走格子 基準(zhǔn)時(shí)間限制：1?秒 空間限制：131072?KB 分值:?5?難度：1級(jí)算法題 ?收藏 ?關(guān)注 有編號(hào)1-n的n個(gè)格子，機(jī)器人從1號(hào)格子順序向后走，一直走到n號(hào)格子，并需要從n號(hào)格子走出去。機(jī)器人有一個(gè)初始能量，每個(gè)格子對應(yīng)一個(gè)整數(shù)A[i]，表示這個(gè)格子的能量值。如果A[i] > 0，機(jī)器人走到這個(gè)格子能夠獲取A[i]個(gè)能量，如果A[i] < 0，走到這個(gè)格子需要消耗相應(yīng)的能量，如果機(jī)器人的能量 < 0，就無法繼續(xù)前進(jìn)了。問機(jī)器人最少需要有多少初始能量，才能完成整個(gè)旅程。 例如：n = 5。{1，-2，-1，3，4} 最少需要2個(gè)初始能量，才能從1號(hào)走到5號(hào)格子。途中的能量變化如下3 1 0 3 7。 Input 第1行：1個(gè)數(shù)n，表示格子的數(shù)量。(1?<=?n?<=?50000) 第2?-?n?+?1行：每行1個(gè)數(shù)A[i]，表示格子里的能量值(-1000000000?<=?A[i]?<=?1000000000) Output 輸出1個(gè)數(shù)，對應(yīng)從1走到n最少需要多少初始能量。 Input示例 5 1 -2 -1 3 4 Output示例 2
【分析】：求前綴和中最小的數(shù)值最后取反，如果都為正，那取較小為0，為負(fù)取反。注意long long。
【代碼】： #include<bits/stdc++.h> using namespace std; int main() { int n; scanf("%d",&n); long long ans=0,sum=0; for(int i=0;i<n;i++) { long long x; scanf("%lld",&x); sum+=x; ans=min(ans,sum); } cout<<-ans<<endl; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/Roni-i/p/7701306.html

總結(jié)

以上是生活随笔為你收集整理的51nod 1344 走格子【贪心/前缀和】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。