OI算法笔记（2）--算法优化

DungDaj

零：文章背景

周末的时候做了一个洛谷题，我的算法和教练给的算法有很大不同....
然后我就想聊一下算法优化的问题（没错就是这么豪横~~~）
题目：洛谷P1424--小鱼的航程(改进版)
一：我的算法

先把原题放出来：


这个题其实不难，题目一放出来我个人的思路是分成三段去求:


先求出第一个不完整周的天数，再求出最后一个不完整周的天数，最后把n个完整周*5就是天数，这样所有的天数就求出来了（一定要注意算完整周的时候是%7而不是%5）。
代码如下：
#include <iostream>
using namespace std;
int main()
{
        int x,n,a,achange,nlast,nwhole,nchange,change;
        //achange:第一个不完整周的里程
        //nlast:最后一个不完整周的工作日天数
        //nwhole:n个完整周--周数
        //nchange:n个完整周+最后一个不完整周的里程
        //change:全部里程
        cin>>x>>n;
        if(x<=5)
        {
                a=6-x; //a就是第一个不完整周的工作日天数
                n=n-a;
                achange=250*a;
        }
        nlast=n%7;
        nwhole=n/7;
        nchange=(nwhole*5+nlast)*250;
        change=achange+nchange;
        cout<<change;
        return 0;
}
这样结果就出来了
然后教练给了我一个鄙视的眼神说...太麻烦了...
二：教练的算法

然后我就拿到了这样的一段代码：
#include <iostream>
using namespace std;
int main()
{
        int x,n,d;
        cin>>x>>n;
        d=n/7*5;
        n%=7;
        if(n>0)
        {
                if(n+x==7||x==7) n--;
                else if(n+x>=8) n-=2;
        }
        cout<<(n+d)*250<<endl;
        return 0;
}
代码分析

d=n/7*5;
n是输入的天数，n/7是计算出来完整周有多少天，最后（*5）得出的是工作日的天数。
（前后拼起来拼成的完整周也算的！）
n%=7;
式子同义为n=n%7，求出的是除去完整周剩余的天数（小于7，包含工作日和休息日！）。
if(n>0)
{
        if(n+x==7||x==7) n--;
        else if(n+x>=8) n-=2;
}
这个就是这部分最不好理解的地方了...
首先，前面n已经取模过了，所以此时n的范围就是[1,6]（没有0是因为if把0过滤掉了）。
1.n+x==7表示的是以周六结束，如图：


上面这个图，以x=6为例，由n+x==7可知此时x=1，表示应该工作一天。但是今天是周六，休息日不工作，所以应该用n--减掉这一天。
同理，其他的也是一样的，可以自己算一算。（很神奇有木有？？？）
2.x==7代表开始的时间是周日
如果开始的时间是周日，那么周日那一天是休息日不工作，所以要从n里面减去周日这一天。
（此处还没理解的请私信我，我单独讲解）
3.n+x>=8代表跨周
如果n+x>=8，那就表示中间跨过了一个周六周日，所以这两天肯定是要减掉的。


如图，3+6=9>8，所以是跨周的；
然后紫色方框框住的两天是休息日，不工作，所以需要减掉这两天不计里程。
这样一顿操作下来后n就是工作日了，最后直接计算里程即可。
三：一个小小的总结

我的算法可能更好想一点，但是论算法复杂度肯定是教练的更简单一点。
考试的时候能想到哪个就写哪个吧，毕竟时间最重要...阿巴

//创作不易，如果赞同的话点个赞同吧嘻嘻！
//原创文章，搬运请提前私信
---------------------------update--------------------------
最后总结的时候写的复杂度是不对的，两个算法复杂度是一样的，不同的是算法的思路和计算的复杂程度，在此感谢大佬 @Alphagocc 的批评指正，谢谢！

闲鱼技术01

你应该是个刚学oier的萌新，还不是很懂复杂度的概念。算法复杂度不是指代码的长短，而是指其实其时间复杂度（也有时指空间复杂度）。这两份代码的时间复杂度是一样的。也就是说在题目给定范围的输入内，这两个代码的运行时间不会有显著差异。
不过教练给了你一段代码，然后你就在学习你和这段代码之间的差异，并比较那个更好，这是值得肯定而且对你未来学习是大有裨益的

BlaXuan

啊是的[大笑]这个我写的时候确实没注意。两份时间复杂度是相同的，谢谢您的指点[赞同][赞同][赞同]