2014年浙江省赛C题,当时觉得难，现在想想这题真水。。
找规律：
若 最大的那个步骤数*m-总和>=0,那么答案就是 最大的那个步骤数 。
否则 就要另加上不够的数量，具体看代码吧，嘻嘻。
下面这个是我比赛时写的，紧张时写的有点冗杂，开心的是一次过了，哈哈。
数组dp[i]是装逼的，保存的是前i个所需的最少时间，貌似除了dp[n-1],前面的都是多余的 - - 。
#include<stdio.h>
#include<string.h>
int main()
{
int t,n,m,maxx,summ,i,a[],dp[],a1,a2;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
memset(dp,,sizeof(dp));
for(i=;i<n;i++)
{
scanf("%d",&a[i]);
}
dp[]=a[];
maxx=a[];
summ=a[];
for(i=;i<n;i++)
{
maxx=maxx>a[i]? maxx:a[i];
summ+=a[i];
int temp=summ-maxx*m,a3=;
if(temp>)
{
a1=temp%m;
a2=temp/m;
a1=(a1>? :);
a3=a1+a2;
}
dp[i]=maxx+a3;
maxx=dp[i];
}
printf("%d\n",dp[n-]);
}
return ;
}
这个是我赛后的精简版本：
#include<stdio.h>
#include<string.h>
int main()
{
int t,n,m,maxx,summ,i,a[];
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
summ=maxx=;
for(i=;i<n;i++){
scanf("%d",&a[i]);
summ+=a[i];
maxx=maxx>a[i]? maxx:a[i];
}
int temp=summ-maxx*m,a1=,a2=;
if(temp>){
a1=temp%m;
a2=temp/m;
a1=(a1>? :);
}
printf("%d\n",maxx+a1+a2);
}
return ;
}
好吧，这题真正需要的就这么点够了'0'
ps：ZJU新校区真大。。。