ZOJ 3778 Talented Chef(找规律，模拟计算，11届ACM省赛，简单)

题目链接

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[40005],dp[40005],a1,a2;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(dp,0,sizeof(dp)); 
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        dp[0]=a[0];
        maxx=a[0];
        summ=a[0];
        for(i=1;i<n;i++)
        {
            maxx=maxx>a[i]? maxx:a[i];
            summ+=a[i];
            int temp=summ-maxx*m,a3=0;
            if(temp>0)
            {
                a1=temp%m;
                a2=temp/m;
                a1=(a1>0? 1:0);
                a3=a1+a2;
            }
            dp[i]=maxx+a3;
            maxx=dp[i];
        }
        printf("%d
",dp[n-1]);
    }
    return 0;
}

这个是我赛后的精简版本：

#include<stdio.h>
#include<string.h>
int main()
{
    int t,n,m,maxx,summ,i,a[40005];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        summ=maxx=0;
        for(i=0;i<n;i++){
            scanf("%d",&a[i]);
            summ+=a[i];
            maxx=maxx>a[i]? maxx:a[i];
        }
        int temp=summ-maxx*m,a1=0,a2=0;
        if(temp>0){
            a1=temp%m;
            a2=temp/m;
            a1=(a1>0? 1:0);
        }
        printf("%d
",maxx+a1+a2);
    }
    return 0;
}

好吧，这题真正需要的就这么点够了'0'

ps：ZJU新校区真大。。。