hihoCoder#1051
剛開始學(xué)習(xí)C語言，準(zhǔn)備在做hiho的題目的過程中來學(xué)習(xí)，在此進(jìn)行記錄，如果代碼中有錯(cuò)誤或者不當(dāng)?shù)牡胤竭€請(qǐng)指正。
描述
小Ho給自己定了一個(gè)宏偉的目標(biāo)：連續(xù)100天每天堅(jiān)持在hihoCoder上提交一個(gè)程序。100天過去了，小Ho查看自己的提
交記錄發(fā)現(xiàn)有N天因?yàn)樨澩嫱浱峤涣恕Ｓ谑切o軟磨硬泡、強(qiáng)忍著小Hi鄙視的眼神從小Hi那里要來M張"補(bǔ)提交卡"。每張
"補(bǔ)提交卡"都可以補(bǔ)回一天的提交，將原本沒有提交程序的一天變成有提交程序的一天。小Ho想知道通過利用這M張補(bǔ)提交
卡，可以使自己的"最長連續(xù)提交天數(shù)"最多變成多少天。
輸入
第一行是一個(gè)整數(shù)T(1 <= T <= 10)，代表測試數(shù)據(jù)的組數(shù)。
每個(gè)測試數(shù)據(jù)第一行是2個(gè)整數(shù)N和M(0 <= N, M <= 100)。
第二行包含N個(gè)整數(shù)a1, a2, ... aN(1 <= a1 < a2 < ... < aN <= 100)，表示第a1, a2, ... aN天小Ho沒有提交程序。
輸出
對(duì)于每組數(shù)據(jù)，輸出通過使用補(bǔ)提交卡小Ho的最長連續(xù)提交天數(shù)最多變成多少。
- 樣例輸入
-
3 5 1 34 77 82 83 84 5 2 10 30 55 56 90 5 10 10 30 55 56 90 - 樣例輸出
- 76
- 59
- 100
解決思路
首先如果m>n,就直接輸出100就可以，否則就要求出最大的連續(xù)天數(shù)。
求解最大的連續(xù)天數(shù)：求出各個(gè)間隔，將任連續(xù)的m+1個(gè)間隔相加，這些連續(xù)間隔的最大值就是最終變成的最大連續(xù)天數(shù)。
#include<stdio.h> int GetMaxNum(int *p,int n,int m); int main() { int n,m,i=0,j,gnum; int *pn,*day; scanf("%d",&gnum); day=(int*)malloc(gnum*sizeof(int)); for(j=0;j<gnum;j++) day[j]=0; while(i<gnum) { scanf("%d%d",&n,&m); pn=(int*)malloc(n*sizeof(int)); for(j=0;j<n;j++) scanf("%d",&pn[j]); day[i]=GetMaxNum(pn,n,m); i++; } for(i=0;i<gnum;i++) printf("%d\n",day[i]); free(pn); free(day); return 0; } int GetMaxNum(int *p,int n,int m) { int i,j,k,day_b[n+1],sumday=0,sumday_l; if(m>=n) return 100; //得到連續(xù)天數(shù)數(shù)組 day_b[n]=100-p[n-1]; j=1; for(i=0;i<n;i++) { day_b[i]=p[i]-j; j=p[i]+1; } //得到m個(gè)連續(xù)間隔之和最大值 for(i=0;i<n+1-m;i++) { sumday_l=0; for(j=i;j<m+i+1;j++) { sumday_l+=day_b[j]; } if(sumday_l>sumday) sumday=sumday_l; } return sumday+m; }
posted on 2015-10-02 21:14 MATHHEW 閱讀(178) 評(píng)論(0) 收藏 舉報(bào)
浙公網(wǎng)安備 33010602011771號(hào)