一.题目
题目描述:
小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 a 道题目,周六和周日每天做 b 道题目。请你帮小明计算,按照计划他将在第几天实现做题数大于等于 n 题?
输入格式:
输入一行包含三个整数 a, b 和 n.
输出格式:
输出一个整数代表天数。
样例输入:
10 20 99
样例输出:
8
提示:
对于 50% 的评测用例,1 ≤ a, b, n ≤ 106 . 对于 100% 的评测用例,1 ≤ a, b, n ≤ 1018 .
二.分析
1.思路1
每天的刷题量都是固定的,最简单的思路就是将一个星期设置为一个循环,前五天每天减去a道题,后两天减去b道题,循环条件是n>0,在设置一个标记函数flag,每减一次,flag++,用来统计天数。这种方法可能是最容易想到的,但是
循环的次数过多,容易超时。
2.思路2
对于这种重复性较高,且数值较大的题目时,我们可以试着
利用题目的重复性,减小数值
,从而达到缩短时间的目的。本题中每天的做题量(n)都是固定的,那么我们可以先算出一个星期能做多少题(a * 5+b * 2),再用总题数除以一星期能做的题数,可以得到需要多少个整星期(w=n/(a * 5+b * 2)),将总题数缩小至一星期以内(n%(a * 5+b * 2)),这样能够大大减少循环次数。
三.代码展示
思路1:
#include<stdio.h>
int main()
{
long long a, b, n;//题目要求的变量(用long long类型是因为题目中有些样例的值可能会过大,使用int会超出范围)
int i = 1;//循环变量1
int flag = 0;//用来统计天数
int j = 0;//循环变量2
scanf("%lld %lld %lld", &a, &b, &n);//输入(注意long long应使用%lld)
while (n>0)//循环条件,当n<0时不再循环
{
for (i = 1; i <= 5 && n > 0; i++)//前五天
{
n -= a;
flag++;
}
for (j = 6; j <= 7 && n > 0; j++)//后两天
{
n -= b;
flag++;
}
}
printf("%d\n", flag);
return 0;
}
思路2:
#include<stdio.h>
int main()
{
long long a, b, n, ret = 0;
scanf("%lld %lld %lld", &a, &b, &n);
int day = 0;
day = n / (a * 5 + b * 2) * 7;//天数
ret = n % ((a * 5 + b * 2) * (day / 7));//剩余的题数
int i = 0;
//相对于思路1少了一个大循环,优化并不彻底
for (i = 0; i < 5 && ret>0; i++)
{
ret -= a;
day++;
}
for (i = 0; i < 2 && ret>0; i++)
{
ret -= b;
day++;
}
printf("%d\n", day);
return 0;
}
思路2(优化):
#include <stdio.h>
int main()
{
long long a, b, n;
scanf("%lld %lld %lld", &a, &b, &n);
long long k = a * 5 + b * 2;//一个星期做题量
long long day = 0;
day += n / k * 7;//天数
n %= k;//一个星期内需要完成的题数
if (n <= a * 5)
{
day += n / a + (n % a != 0);//n%a!=0是指不能整除还需要一天(如前五天每天做3题,还剩下7题,7/3=2...1,剩下的那一题还需要一天)
}
else
{
n -= a * 5;//减去前面五天的题目
day += 6 + (n > b);//进入else语句说明剩下的题目至少需要一天,如果剩下的题数一天内完成不了,那么肯定得两天内完成
}
printf("%lld\n", day);
return 0;
}
最后:
每日一题系列旨在养成刷题的习惯,所以对代码的解释并不会特别详细,但足够引导大家写出来,选的题目都不会特别难,但也不是特别简单,比较考验大家的基础和应用能力,我希望能够将这个系列一直写下去,也希望大家能够和我一起坚持每天写代码。
在这里送大家一句话:
广积粮,缓称王!