「计算机问题求解：使用C语言」是NJUPT软件工程专业第一学期的通识课，主播这门课的老师是蔡慧老师。

前几天，学校开放了两年来期中考试的题目的OJ，主播做了一下，发现除了每年的最后一题上对时间复杂度有要求之外，其余的题目考查的是C语言基本语法，几乎不涉及比较复杂的程序设计，但是每年的最后一两题是值得思考一下的。

2024年第三题：#C. 炒股收益问题

题目描述

某同学生活在美丽的仙林，突发奇想想到了炒股。他运用了神奇魔法获取了一支股票未来连续 N 天的价格。现在想知道从这 N 天里，哪天买入，哪天卖出可以使自己的收益最大。

输入格式

输入第一行是一个整数 T，代表测试用例个数。接下来的每组数据第一行为一个整数 N(2≤N≤100000)N(2≤N≤100000)，代表这支股票未来 N 天的价格，第二行为 N 个整数a1,a2,⋯ ,aNa1,a2,⋯,aN。

输出格式

输出该同学能得到的最大收益。如果他无论怎么买入卖出都不能赚钱（收益大于 00），输出 00。

输出格式如样例所示。先输出 Case,再输出测试号，最后输出答案。

输入输出样例

3
3
3 2 1
3
1 2 3
3
2 3 1

Case 1: 0
Case 2: 2
Case 3: 1

说明/提示

时间限制：1s，空间限制：64M

解析

时间复杂度O(n^2)的算法很容易想到，但是最后一个测试点会超时，无法拿到满分，所以必须降低时间复杂度。

所以应该思考：如何仅使用一次遍历就得出答案？即在读取输入的同时进行计算并得出答案？

可行性：这个想法是可行的，因为基于到某个时刻已经输入的数据可以得出局部最优解，之后要做的就是在读取后续输入的同时不断更新答案。

分析：

• 局部最优解取决于已经输入的数据中的最小值和其之后的最大值，也就是说确定一个最小值之后，答案取决于这个最小值之后的最大值。
• 如何在遍历中确立最小值？只需要在读取数据的同时不断和前面已经确定的最小值不断比较即可。
• 如何在确定最小值之后确定最大值？维护一个局部最大值是否可行？不可行，因为最小值更新的时候维护的最大值（处于先前的最小值后面，现在的最小值前面）就失效了！
• 所以可以在之后每次读取之后都直接计算答案，并维护一个当前读取数据与最小值之差的最大值，这样就可以保证得到的答案确实是局部最优解，并在读取全部数据后优化为全局最优解。
• 原理：始终确保买入的时候是此时的最小值，卖出的时候是收益最高的时候。
• 为什么这个算法能降低时间复杂度？每排除一个买入的天数（非最小值的天数），实际上排除了以这个天数为起点的所有情况。
  
• 这种算法实际上是双指针，慢指针指向局部最小值，快指针遍历数组，当最小值更新后，将最大值重新开始计数

我的代码

#include<stdio.h>
#include<math.h>

int main () {
    int num ;
    scanf("%d",&num);
    for(int i = 0 ; i<num ; i ++ ){
        int days,min,temp,profit=0;
        scanf("%d",&days);
        scanf("%d",&min);
        for(int day = 1 ;day<days ; day++){
            scanf("%d",&temp);
            min = temp<min?temp:min;
            profit = (temp-min)>profit?(temp-min):profit ;
        }
        printf("Case %d: %d\n",i+1,profit);
    }
    return 0 ;
}

2023年第四题：#D. 该加训数理基础了

题目描述

zy同学想成为一名数学大师，但他看到诸如莫比乌斯反演，Min_25筛，快速傅里叶变换，快速沃尔什变换，多项式牛顿迭代，多项式多点求值，狄利克雷生成函数，范德蒙德卷积等一系列名字都看不懂的东西时，他明白，自己的路还有很长，于是，他就准备从最基础的学起。最近，zy同学在学习时遇到了个很有意思的题：

有n,k两个整数

他想知道末尾至少有连续 k 个 00，并且可以被 n 整除的最小正整数。

例如，当 n\=375,k\=4 时，满足条件的最小正整数为 30000。

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据占一行，包含两个整数 n,k。

输出格式

每组数据输出一行结果，表示满足条件的最小正整数。

数据范围

保证40%数据满足 1≤T≤10，1≤n≤100，0≤k≤2。

所有数据满足 1≤T≤10 ⁵，1≤n≤10⁹，0≤k≤9。

输入样例

6
375 4
10000 1
38101 0
123456789 8
1 0
2 0

输出样例

30000
10000
38101
12345678900000000
1
2

解析

最容易想到的方法是从1开始遍历，这种方法的时间复杂度对k来说是指数级别的，对n是线性的，显然会严重超时。

对这种方法的改进很简单，result的最后一定有k个0，所以可以遍历除0之外的数，这种方法的时间复杂度对n是线性的，但是仍然会超时。

另外，值得注意的是，答案可能会超过int的范围，所以对答案的存储应该使用long int。

那么，能获得全部AC的算法应该怎样设计呢？不妨分析一下：

• 「整除」指的是n的因子是result的子集
• result可以写成r2 ^r1*5^r2的形式，n可以写成num*2ⁿ¹\5ⁿ²的形式
• 这样，这道题目就迎刃而解了，我们只要补足result相对n中缺少的因子即可
• 先计算出num、n1、n2，然后将num与2和5因子差项补足的乘积赋值给r即可
• 这样，时间复杂度就降到了对数级别

我的代码

#include<stdio.h>
#include<math.h>

int main () {
    int num ;
    scanf("%d",&num);

    for(int i = 0 ; i < num ; i ++){
        int n,k,temp;
        scanf("%d %d",&n,&k);

        temp=n ;
        int n_2=0,n_5=0;
        while(temp%2==0){
            temp/=2;
            n_2++;
        }
        while(temp%5==0){
            temp/=5;
            n_5++;
        }

        int correct = pow(2,fmax(0,n_2-k)) * pow(5,fmax(0,n_5-k)) ;

        long int result = pow(10,k) * temp * correct; ;
        printf("%ld\n",result);
    }
    return 0 ;
}