【C语言】临时记忆：用数组实现队列功能的解法 - DotcppXF

【解题思路】

        ① 用数组 a[] 标记目前所有书的状态，便于查找，提高效率；

        ② 用数组 b[] 储存小A记住的书，循环处理完他需要依次记住的书。

【1】所有书的状态标记

        ① 实际上数组 b[] 已经储存了小A记住的书了，但每次面对新书的时候都需要用 for 循环查找一遍已经记住的书，效率很低。因此不如多开一个数组记录所有书的状态，初始化所有书本 a[i]=0 ，若书本 i 被小A记住了，则 a[i]=1 ，数组 a[] 开3000以上就可以了，因为题目中说明了输入的 ki<=3000。

scanf("%d",&b[i]);                         // 依次输入需要记住的书
if(a[b[i]]==0)                             // 若此本书没记住过，s加1，表示需要多看1次书
{
    s++;
    a[b[i]]=1;                             // 标记此书记住了
}
else                                       // 若此本书已经记住了，当压根没输入过这本书
{
    i--;
    n--;                                   // n表示要输入的书的数量，若i减1了，n也要跟着减1
}

【2】处理遗忘掉的书

        ① 若 i<m 表示还可以继续记新的书，若 i>=m 表示需要开始遗忘书了，也就是每次遗忘 b[i-m] 这本：

if(i-m>=0)
    a[b[i-m]]=0;                           // 标记b[i-m]这本书被忘记了

【注意事项】

        ① 采用标记的方法时要注意数据的取值范围，若太大或者没有数据范围，则此方法不可行。

【参考代码】

#include<stdio.h>

int main(void)
{
    int a[3001]={0},b[10001],n,m,s=0;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&b[i]);                  // 依次输入n本需要记住的书
        if(a[b[i]]==0)                      // 若没记住，则次数加1
        {
            s++;
            a[b[i]]=1;                      // 标记记住的书
        }
        else                                // 若记住了，则不处理
        {
            i--;
            n--;
        }
        if(i-m>=0)                          // 标记遗忘的书
            a[b[i-m]]=0;
    }
    printf("%d",s);
    return 0;
}