解题思路:
首先我们在考场上面首先想到的肯定是循环没错了,但是这题目出的很巧妙n的最大值大到了1018所以数据量太大了,我们就不能简单的用循环来做了.
思路一:暴力循环(只能拿80分,时间超限了)
思考一下我们循环的目的是什么?不就是为了从第1天算到答案所需要的那一天,然后一星期一星期的循环,那我们直接利用除法和求余就可以代替循环的过程对吧.
先给大家看下循环做法,写的可能很繁琐,但是过程很清晰(只能拿80分,很明显时间超限了)
#include<stdio.h>
long long int f(long long int n,long long int a,long long int b) //n代表总题数,a代表星期一到星期五做的题的数量,b代表星期六和星期天做题的数量
{
int flag;
long long int sum=0; //flag用来记录最后是在1-5停的,还是在6-7停的
while(n!=0)
{
n-=5*a; //先算1-5
if(n<0)
{
flag=1;
break;
}
sum+=5;
n-=2*b; //再算6-7
if(n<0)
{
flag=2;
break;
}
sum+=2;
}
if(flag==1) //如果是在1-5停的话
{
n+=5*a; //加回来,然后算是在第几天的
while(n>a)
{
n-=a;
sum++;
}
sum++; //不满一天就加回去
}
else if(flag==2)
{
n+=2*b;
while(n>b)
{
n-=b;
sum++;
}
sum++;
}
return sum;
}
int main()
{
long long int a,b,n;
scanf("%lld%lld%lld",&a,&b,&n);
printf("%lld",f(n,a,b));
return 0;
}看起来上面的循环来做时间复杂度是o(n/(a+b)),前提是你用int类型的数据,它占了四个字节,运行会快一点,但是你改成long long int的话占16个字节,所以运行起来更慢,肯定就超时了
思路二:利用flag记录来避过循环(满分AC):
所以我们换到另一种思路直接利用flag我们记录总共可以进行多少个完全周(指的是1-7全部完成的),然后直接算最后那一周就刚好避过了循环:
flag=n/(a*5+b*2); //flag就是记录总共可以进行多少个完全周 n-=(a*5+b*2)*flag; //然后直接减 sum+=flag*7; //sum就要加上进行的天数
代码实现:
#include<stdio.h>
int main()
{
long long int a,b,n,sum=0;
scanf("%lld%lld%lld",&a,&b,&n);
long long int flag=n/(a*5+b*2);
n-=(a*5+b*2)*flag;
sum+=flag*7;
if(n/a<=5)
{
sum+=n/a;
if(n/a==5)
{
sum+=(n-5*a)/b+(n-5*a-b)%1;
}
else if(n%a>0)
{
sum++;
}
}else{
sum+=5+(n-5*a)/b;
if((n-5*a)%b>0)
{
sum++;
}
}
printf("%lld",sum);
return 0;
}0.0分
48 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
@killer #include<stdio.h> int main() { long long int a,b,n,sum=0; scanf("%lld%lld%lld",&a,&b,&n); long long int flag=n/(a*5+b*2); n-=(a*5+b*2)*flag; sum+=flag*7; if(n/a<=5) { sum+=n/a; if(n/a==5) { sum+=(n-5*a)/b; n = (n-5*a)/b; if(n % b > 0) { sum++; } } else if(n%a>0) { sum++; } }else{ sum+=5+(n-5*a)/b; if((n-5*a)%b>0) { sum++; } } printf("%lld",sum); return 0; }//现在sum=flag*7; if (n <= 5 * a) { if ((n % a) == 0) { printf("\n%lld\n", sum + n / a); } else { printf("\n%lld\n", sum + 1 + n / a); } } else { long long int temp = n - 5 * a; if (temp <= b) { printf("\n%lld\n", sum + 6); } else { printf("\n%lld\n", sum + 7); } } 这样为什么会显示错误？这一串是用来做什么的 if(n/a==5) { sum+=(n-5*a)/b+(n-5*a-b)%1; }#include<stdio.h> int main() { long int a,b,n,i,w,s=0; scanf("%ld %ld %ld",&a,&b,&n); w=n/(5*a+2*b); s=w*(5*a+2*b); for(i=1;i<8;i++){ if(i%7==6||i%7==0){ s+=b; } else{ s+=a; } if(s>=n){ printf("%ld",7*w+i); return 0; } } return 0; }#include<stdio.h> int main() { long long int a,b,n; scanf("%lld%lld%lld",&a,&b,&n); long long int sum=5*a+2*b; long long int ans=7*(n/sum); n=n%sum; long long int d[]={a,a,a,a,a,b,b},i; for(i=0;n>0;i++) { n-=d[i]; ans++; } printf("%lld",ans); return 0; }#include<stdio.h> int main() { long long int a,b,n; scanf("%lld%lld%lld",&a,&b,&n); long long int sum=5*a+2*b; long long int ans=7*(n/sum); n=n%sum; long long int d[]={a,a,a,a,a,b,b},i; for(i=0;n>0;i++) { n-=d[i]; ans++; } printf("%lld",ans); return 0; }简单的算法，虽然只能拿80分 #include <stdio.h> void main() { long long a,b,n; long long i, sum=0,days=0; scanf("%lld%lld%lld",&a,&b,&n); for(i=1;i<=7;i++) { days++; if(i<=5) sum+=a; if(i>5&&i<=7) sum+=b; if(i==7) i=0; if(sum>=n) break; } printf("%lld",days); }