1192: 锘爺考駕照
時間限制: 1 Sec 內(nèi)存限制: 128 MB
提交: 1766 解決: 416
[提交][狀態(tài)][討論版]
題目描述
大家都知道，锘爺是XDUdp第一人，所以锘爺決定要去考駕照！（這很有邏輯吧），他為了一次考到駕照，于是買了一輛越野車從學(xué)校開回家來練習(xí)開車，在途中就會有很多高山和低谷（低谷可能比地平面低）。經(jīng)過一段時間的調(diào)查，現(xiàn)在他已經(jīng)知道了最短的路線，我們假設(shè)這是一條直線，并且他一定會走這條直線。但是這也太遠了，锘爺想找一段開車的時間打瞌睡，為了更舒服的打瞌睡，于是锘爺統(tǒng)計了這條路線上所有的山峰和谷底的高度，他想知道長度為length的路上高度之和最小的一段是多少？

輸入
多組數(shù)據(jù)（不超過50組），處理到文件結(jié)束。
對于每組數(shù)據(jù)，讀入一個整數(shù)n，length(1<=length<=n<=200000)n表示山峰和低谷數(shù),length表示諾爺打瞌睡的長度。
接下來是n個整數(shù)h(i)，表示高度，abs(h(i))<=200000。

輸出
對于每組數(shù)據(jù)，輸出一個整數(shù)表示長度為length高度和的最小值。

樣例輸入
3 2
1 2 3
5 3
1 -1 -1 2 -5
樣例輸出
3
-4
提示
來源
sublimation

#include<stdio.h> #include<math.h> #include<string.h> #define max(a,b) (a>b)? b:a int bes=2000000; int main() {int n,length,i,j;while(scanf("%d %d",&n,&length)!=EOF){int h[n];int sum[n-length+1];for(i=0;i<n;i++)scanf("%d",&h[i]);memset(sum,0,sizeof(sum));for(i=0;i<n-length+1;i++){for(j=0;j<length;j++){sum[i]+=h[i+j];}bes=max(bes,sum[i]);}printf("%d\n",bes);}return 0;} //時間超限 #include<stdio.h> #include<math.h> #include<string.h> #define max(a,b) (a>b)? b:a int main() {int n,length,i,j;while(scanf("%d %d",&n,&length)!=EOF){int h[n];long long sum=0,bes=0;for(i=0;i<n;i++)scanf("%d",&h[i]);if(n==length){for(i=0;i<n;i++)bes+=h[i];}else{for(i=0;i<length;i++){sum+=h[i];}bes=sum;for(j=0;j<n-length;j++){sum=sum-h[j]+h[j+length];bes=max(bes,sum);}}printf("%lld\n",bes); }return 0;}

總結(jié)

以上是生活随笔為你收集整理的xdoj 1192: 锘爷考驾照的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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