【CSDN周赛】第21期第二题千问万问

淩亂°似流年 2023-10-11 20:26 23阅读 0赞

**题目描述：**

给定大小为n的整数序列A. 现在会有q次询问，询问子区间的整数数量。

**思路：**

1、考的时候没做出来，但是感觉不难，一直不懂错在哪里，所以比赛结束后继续修改；

2、以下代码没有按调用函数的方法做，直接在主函数里写了；

3、题目给的主函数在给str2赋值的时候写成了str\[q\]\[0\]和str\[q\]\[1\]，应该改为str\[i\]\[0\]和str\[i\]\[1\]（回不到竞赛的编译环境了，我是从报告里复制出来发现的，也可能是自己不小心改错成q了）；

4、特别要注意：

（虽然对指针变量存放地址有简单了解，但对于数组指针的掌握不是很深刻，先死记以下形式）

1）若 **int \*arr1**

则赋值时可以用 **arr1\[i\]** 或 **\*(arr1+i)**

扩容可以用 **arr1 = (int\*)malloc(n \* sizeof(int));**

2）若 **int (\*arr2)\[2\]**

则赋值时可以用 **arr2\[i\]\[1\]** 或 **\*(\*(arr2+i)+1)**，但**不能用 \*(\*arr2+i)+1)**

扩容可以用 **arr2 = (int(\*)\[2\])malloc(q \* sizeof(int \*))**

5、整道题的思路主要是判断序列A有多少个元素在区间内

1）先对A进行排序，这样当arr1\[j\]>arr2\[i\]\[1\]时就不用继续遍历后面的元素了，所以下面的代码其实还可以再优化下；

2）对每组区间，都对A重复进行遍历。既然是要求在区间的元素数量，若区间组的范围集中，可以参考素数筛的方法再优化下代码。

6、题海战术效果不明显，应当是掌握一定的基础知识后，通过学习他人优秀的解题方法和思路，举一反三地刷题，而非低效地通过代码shi山去解题。后续应多学习别人的长处，内化为自己的东西，希望自律一些，再接再厉吧。

**编写的代码：**

#include <stdio.h>
    #include <stdlib.h>
    
    int main()
    {
        int n, q, i, j;
        scanf("%d %d", &n, &q);
        int *arr1;
        arr1 = (int*)malloc(n * sizeof(int));
        for (i = 0; i < n; i++)
            {
              scanf("%d", &arr1[i]);
            }
    
        int (*arr2)[2];
        arr2 = (int(*)[2])malloc(q * sizeof(int *));//注意最后一个*不能舍去！
        for (i = 0; i < q; i++)
            {
            int l, r;
            scanf("%d %d", &l, &r);
            arr2[i][0] = l;
            arr2[i][1] = r;
            }
        /*
        for(int i=0;i<q;i++) 
        {
          printf("@@@%d@@@",arr2[i][1]);//正确
          printf("&&&%d&&&",*(*arr2+i)+1); //错误
          printf("###%d###",*(*(arr2+i)+1)); //正确
        }
        */
    
       //先对arr1从小到大排序
        for(i=0;i<n;i++){
            for(j=i+1;j<n;j++){
                if((*(arr1+i))>(*(arr1+j))){
                    int temp;
                    temp=*(arr1+i);
                    *(arr1+i)=*(arr1+j);
                    *(arr1+j)=temp;
                    }
        }
        }
    
        //计算每行区间的元素个数
        for(i=0;i<q;i++){
            int count=0;//每行区间的元素个数
            for(j=0;j<n;j++){
                if((arr2[i][0]<=arr1[j])&&(arr1[j]<=arr2[i][1]))
                    count++;
            }
            printf("%d\n",count);
        }
        return 0;
    }

**运行结果：**

![7ef103faba474bd1bc1a320005e44342.png][]

[7ef103faba474bd1bc1a320005e44342.png]: https://img-blog.csdnimg.cn/7ef103faba474bd1bc1a320005e44342.png