CCF-CSP认证试题——分蛋糕
思路
有n块蛋糕分给若干个人,具体多少人需要我们统计,每个人分得蛋糕的重量大于k,除非没有蛋糕了。根据这样的要求,我们可以认为分完一个人的蛋糕,就把那几块蛋糕视为扔掉了。具体怎么统计呢?我们可以用for循环遍历这n块蛋糕,用sum统计蛋糕重量,大于k了,就分给一个人,人数p加1,然后把sum置零;如果没有大于k,就拿着sum去加下一块蛋糕,然后在进行判断。
注意,跳出循环的情况有两种:一是蛋糕分完了,都分得大于等于k,此时sum=0;二是最后1块或多块加起来还小于k,此时sum>0。
#include <iostream>
#include<cstdio>
using namespace std;
int a[1001]; //注意a[i]的大小
int main()
{
int n,k,p=0,sum=0,s=0; //p统计人数,sum记录蛋糕重量,s可有可无,为了保存sum
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(int j=0;j<n;j++)
{
sum += a[j];
s = sum;
if(sum>=k)
{
p++;
sum = 0;
}
}
printf("%d",s<k?p+1:p);
}
评分
问题和分析
第一次提交时只得了20分,分析了一下代码,自己编了几组样例,感觉并没有错误,后来看了看题目中的样例规模,才发现我定义的a[1000]比规模小了1个,改成a[1001]就满分了,所以说在允许的范围内不要吝惜空间。