[已解决]复杂循环数组

不爱听课的同学

这道题实在不会做啦 ，求大佬给予一些思路，能有代码就更好了
初始难度


难度升级


代码长度限制
16 KB
时间限制
200 ms
内存限制
64 MB

最佳答案

月排行榜 / 总排行榜

gonff

2020-11-21 02:27:17

我的想法：
设置一个盒子，可以加入和排出序列。其关键因素是头（begin），尾（end）位置，以及二者之间元素的和（sum）。
盒子有两个基本能力：
        排出数字：其实就是特殊的移动，sum=sum-a[begin];begin+=1;
        吞入数字：sum=sum+a[end+1];end+=1;
二者组合可以变成“移动”：sum=sum+a[end+1]-a[begin];begin+=1;end+=1; （最好不要把盒子设置成a(begin)到a(end)的数组，那样更新太慢了。）
1、首先应该从头开始，一个个吞入数字，直到sum>=S，于是现在盒子头在第begin=1个，尾则在第end个。 #从现在开始，在任何情况下都不能再吞入了，因为我们题目要求找最小的盒子。
2、接下来从头部开始，一个一个排出数字，sum相应的减少，直到不能排出（也就是排出下一个就会sum<S）。这时有新的begin。
3、把当前的begin和end保存在destination里面
4、关键一步，盒子向右移动一格，比较a(begin-1) 和 a(end)，也就是比较新加入的数字和移除的数字谁更有价值，或者说更大。然后依据情况跳入下面两种中的一种：
     若a(end)>a(begin-1)：进入4.1。
     若a(end)<a(begin-1)：进入4.2。
4.1 也就是说接下来有可能可以排出数字，开始尝试排出数字。若成功排出（无论排出几个）则回到第3步更新destination。没有排出则回到第4步。
4.2 新加入的数字其实没什么价值，无法排出数字。进行下一步判断，是否还满足sum>=S。若满足则跳入第4步判断，若不满足继续第4.2步。（这个判断其实减少了很多计算，你不用强行把盒子扩充到满足条件为止，我们题目要求盒子的长度只减不增）。

基本上就是这个思路。代码实现要加一下跳出结束条件，或者判断到结尾不可吞入了，或者什么情况时不可排出了，之类的。依据你的设计可能会占用不同的时间。

时间考量：
大概想了一下，第4步比较行为大概是2n次（每个数字作为先作为尾巴后面那个数字，后面又要作为头部）。
盒子的更新，吞入和排出其实很少发生，主要考虑移动，应该是4n次的感觉? sum=sum+a[end+1]-a[begin];begin+=1;end+=1;加法记得是一步步加的，所以3个式子实际计算了4次。
总之这个思路下，所有行为都是O(n）的。总的来说也就应该是O(n)的。

跳转到最佳答案楼层

Cool_Breeze

抱歉，我连题都没有看懂题！

不爱听课的同学

Cool_Breeze 发表于 2020-11-20 17:19
抱歉，我连题都没有看懂题！

抱歉，是我的疏忽，我已经上传了更详细的题目啦

gonff

我的想法：
设置一个盒子，可以加入和排出序列。其关键因素是头（begin），尾（end）位置，以及二者之间元素的和（sum）。
盒子有两个基本能力：
        排出数字：其实就是特殊的移动，sum=sum-a[begin];begin+=1;
        吞入数字：sum=sum+a[end+1];end+=1;
二者组合可以变成“移动”：sum=sum+a[end+1]-a[begin];begin+=1;end+=1; （最好不要把盒子设置成a(begin)到a(end)的数组，那样更新太慢了。）
1、首先应该从头开始，一个个吞入数字，直到sum>=S，于是现在盒子头在第begin=1个，尾则在第end个。 #从现在开始，在任何情况下都不能再吞入了，因为我们题目要求找最小的盒子。
2、接下来从头部开始，一个一个排出数字，sum相应的减少，直到不能排出（也就是排出下一个就会sum<S）。这时有新的begin。
3、把当前的begin和end保存在destination里面
4、关键一步，盒子向右移动一格，比较a(begin-1) 和 a(end)，也就是比较新加入的数字和移除的数字谁更有价值，或者说更大。然后依据情况跳入下面两种中的一种：
     若a(end)>a(begin-1)：进入4.1。
     若a(end)<a(begin-1)：进入4.2。
4.1 也就是说接下来有可能可以排出数字，开始尝试排出数字。若成功排出（无论排出几个）则回到第3步更新destination。没有排出则回到第4步。
4.2 新加入的数字其实没什么价值，无法排出数字。进行下一步判断，是否还满足sum>=S。若满足则跳入第4步判断，若不满足继续第4.2步。（这个判断其实减少了很多计算，你不用强行把盒子扩充到满足条件为止，我们题目要求盒子的长度只减不增）。

基本上就是这个思路。代码实现要加一下跳出结束条件，或者判断到结尾不可吞入了，或者什么情况时不可排出了，之类的。依据你的设计可能会占用不同的时间。

时间考量：
大概想了一下，第4步比较行为大概是2n次（每个数字作为先作为尾巴后面那个数字，后面又要作为头部）。
盒子的更新，吞入和排出其实很少发生，主要考虑移动，应该是4n次的感觉? sum=sum+a[end+1]-a[begin];begin+=1;end+=1;加法记得是一步步加的，所以3个式子实际计算了4次。
总之这个思路下，所有行为都是O(n）的。总的来说也就应该是O(n)的。

gonff

比如你给的第一个输入， 我来描述一下：
首先吞入前5个数字，盒子的状态是(begin, end, sum)=(0, 4, 24)
然后排出数字之后，盒子的状态是（3，4, 15）。
destination=(3, 4)
移动一格 ,变成(4, 5, 17)，判断7>5所以开始尝试排出，无法排出；
继续移动，变成(5, 6, 11), sum<S，所以继续移动。
等等，
执行到最后destination=(3, 4)不变。
于是输出长度length=4 - 3 + 1=2， 序列为[a[3],a[4]]也就是[5, 10]

gonff

试着写了一下代码。没有加入输入部分，只是初始化了一下。你可以把数组改一改，如果满足要求，就自己再加入一些语句修饰一下。

#include <stdio.h>

//用指针比较方便返回数组
int * find(int n, int S, int a[]) {
        //初始化盒子参量
        int begin = 0;
        int end = 0;
        int sum = a[0];

        int destination[3] = { 0, 0, 0 };//最终返回的数组：第一二分量是盒子的开头和结尾，第三分量标记是否溢出。

        //开始吞入：
        for (; sum < S;) {
                if (end < n-1) {
                        end++;
                        sum += a[end];
                }
                else { destination[2] = -1; break; };
        };
        //printf("吞入完成后end=%d\n", end);

        //开始排出；
        for (; sum >= S; begin++) {
                if (sum - a[begin] >= S) {
                        destination[0] = begin+1;
                        destination[1] = end;
                        sum -= a[begin];
                        //printf("排出一次begin=%d\n", begin);
                }
                else { break; };
        };

        //printf("本次排出后begin=%d\tend=%d\n", begin,end);

        
        //开始移动判断的循环
        for (; end < n-1;) {
                sum = sum + a[end + 1] - a[begin];
                end++;
                begin++;
                //printf("移动结果end=%d", end);
                if (a[end] > a[begin - 1]) {
                        for (; sum >= S; begin++) {
                                if ((sum - a[begin]) >= S) {
                                        destination[0] = begin+1;
                                        destination[1] = end;
                                        sum -= a[begin];
                                        //printf("排出一次begin=%d\n", begin);
                                }
                                else { break; };
                        };
                };
        };
        return destination;
}

void main() {
        //初始化数据
        int n = 9;
        int S = 15;
        int a[] = { 1, 1, 3, 5, 10, 13, 19, 19, 5};
        int sizea;
        sizea = sizeof(a) / sizeof(int);
        if (n != sizea) {
                printf("尺寸不对，已改正n=%d\n", sizea);
                n = sizea;
        };


        //指针用于返回数组
        int *p;
        p = find(n, S, a);
        if (*(p+2) == -1) {
                printf("%d\n", 0); printf("%d\n", 0);
        }
        else {
                int destination[2] = { 0, 0 };
                destination[0] = *p;
                destination[1] = *(p + 1);
                //printf("destination[0]=%d\n", destination[0]);
                //printf("destination[1]=%d\n", destination[1]);
                int len;
                len = destination[1] - destination[0] + 1;

                //打印结果
                int i = 0;
                printf("%d\n", len);
                if (len > 1) {
                        for (; i < len - 1; i++) {
                                printf("%d", a[destination[0] + i]);
                        };
                }
                else { printf("%d", a[destination[0]]); };
        };
}

不爱听课的同学

gonff 发表于 2020-11-21 02:27
我的想法：
设置一个盒子，可以加入和排出序列。其关键因素是头（begin），尾（end）位置，以及二者之间元 ...

今天下午用你的思路写了这个代码，没想到超时了，题目限制200ms，但我花了318ms。不过还是很感谢你的详细解答，让我见识到了这么奇妙的做法，下面是我写的代码。
ps:我觉得我可能是没领悟到你的思路，其实我没看懂为什么4.2中不满足sum>=S就继续4.2步，我觉得不满足的话就继续右移盒子直到sum>=S再判断新加入的数字和移除的数字谁更大，可能是因为没弄懂这点才超时吧。

#include <iostream>
using namespace std;
int num[50][1000000];
int main()
{
        int N, lens[50][2], begin = 0, end = 0, sum, Begin, End;   //lens[50][2]储存数组长度和整数S  Begin和End存储起始点和结尾点
        cin >> N;
        for (int i = 1;i <= N;i++) {         //数组录入       
                cin >> lens[i][0] >> lens[i][1];
                for (int j = 0;j < lens[i][0];j++) cin >> num[i][j];
        }

        int len, S;
        for (int i = 1;i <= N;i++) {    
                len = lens[i][0];S = lens[i][1];
                begin = 0;end = 0;sum = 0;
                Begin = 0;End = 0;
                for (int j = 0;sum < S && j < len;j++) {      //吞入数字
                        sum += num[i][j];
                        end = j;
                }

                if (sum < S) {         //判断是否存在大于整数S的序列
                        cout << 0 << endl << 0;
                        if (i != N) cout << endl;
                        continue;
                }

                while (1) {           //移出数字
                        if ((sum - num[i][begin]) >= S) {
                                sum -= num[i][begin];
                                begin++;
                        }
                        else break;
                }
                Begin = begin;End = end;

                while (begin < len - 1) {
                        begin++;end++;                        //右移盒子
                        sum -= num[i][begin - 1];sum += num[i][end];

                        if (sum >= S) {
                                if (num[i][end] > num[i][begin - 1]) {     //若新加入的数字比移除的数字更大
                                        while (1) {
                                                if ((sum - num[i][begin]) >= S) {  //判断是否可以移除数字
                                                        sum -= num[i][begin];
                                                        begin++;
                                                        Begin = begin;End = end;
                                                }
                                                else break;
                                        }
                                }
                        }
                }

                cout << End - Begin + 1 << endl;     //输出结果
                for (int j = Begin;j <= End;j++) {
                        cout << num[i][j];
                        if (j == End) cout << endl;
                        else cout << ' ';
                }
        }
        return 0;
}

gonff

你说的很对啊。4.2之后不用跳回4.2，直接回4，就少了一次判断，节约好多时间呢。 学到了。

不爱听课的同学

gonff 发表于 2020-11-21 12:30
试着写了一下代码。没有加入输入部分，只是初始化了一下。你可以把数组改一改，如果满足要求，就自己再加入 ...

我昨晚把你的代码改了一下交了上去，结果显示段错误，而且也超时了，刚刚我用前缀和写了一下又超时了，真的肝不动这道题啦。

修改后的代码如下

#include <iostream>
using namespace std;
int num[50][1000000];
//用指针比较方便返回数组
int* find(int n, int S, int a[]) {
    //初始化盒子参量
    int begin = 0;
    int end = 0;
    int sum = a[0];

    int destination[3] = { 0, 0, 0 };//最终返回的数组：第一二分量是盒子的开头和结尾，第三分量标记是否溢出。

    //开始吞入：
    for (; sum < S;) {
        if (end < n - 1) {
            end++;
            sum += a[end];
        }
        else { destination[2] = -1; break; };
    };
    //printf("吞入完成后end=%d\n", end);

    //开始排出；
    for (; sum >= S; begin++) {
        if (sum - a[begin] >= S) {
            destination[0] = begin + 1;
            destination[1] = end;
            sum -= a[begin];
            //printf("排出一次begin=%d\n", begin);
        }
        else { break; };
    };

    //printf("本次排出后begin=%d\tend=%d\n", begin,end);


    //开始移动判断的循环
    for (; end < n - 1;) {
        sum = sum + a[end + 1] - a[begin];
        end++;
        begin++;
        //printf("移动结果end=%d", end);
        if (a[end] > a[begin - 1]) {
            for (; sum >= S; begin++) {
                if ((sum - a[begin]) >= S) {
                    destination[0] = begin + 1;
                    destination[1] = end;
                    sum -= a[begin];
                    //printf("排出一次begin=%d\n", begin);
                }
                else { break; };
            };
        };
    };
    return destination;
}

int main() {
    //初始化数据
    int N, lens[50][2];   //lens[50][2]储存数组长度和整数S
    cin >> N;
    for (int i = 1;i <= N;i++) {         //数组录入
        cin >> lens[i][0] >> lens[i][1];
        for (int j = 0;j < lens[i][0];j++) cin >> num[i][j];
    }

    int n, S;
    for (int i = 1;i <= N;i++) {
        n = lens[i][0];S = lens[i][1];
        int* p;
        p = find(n, S, num[i]);
        if (*(p + 2) == -1) {
            cout << 0 << endl << 0 << endl;
        }
        else {
            int destination[2] = { 0, 0 };
            destination[0] = *p;
            destination[1] = *(p + 1);
            //printf("destination[0]=%d\n", destination[0]);
            //printf("destination[1]=%d\n", destination[1]);
            int len;
            len = destination[1] - destination[0] + 1;
            //打印结果
            cout << len << endl;
            for (int j = destination[0];j <= destination[1];j++) {
                cout << num[i][j];
                if (j == destination[1]) cout << endl;
                else cout << ' ';
            }
        }
    }
    return 0;
}

赚小钱

非常典型的滑动窗口问题，双指针套路。使用关键字能搜索出一大把代码，自己写吧。

过，下一题。

gonff

找到几个可以改进的点。
1、

    //开始排出；
    for (; sum >= S; begin++) {
        if (sum - a[begin] >= S) {
            destination[0] = begin + 1;
            destination[1] = end;
            sum -= a[begin];
            //printf("排出一次begin=%d\n", begin);
        }
        else { break; };
    };

改成:

    //开始排出；
    for (; sum -a[begin] >= S; ) {
            destination[0] = begin + 1;
            destination[1] = end;
            sum -= a[begin++];
            //printf("排出一次begin=%d\n", begin);
    };

少了一次判断，还有else也没了。后面移动中的排出也是一样。

2、

    //开始移动判断的循环
    for (; end < n - 1;) {
        sum = sum + a[end + 1] - a[begin];
        end++;
        begin++;

改成

    //开始移动判断的循环
int n1 = n - 1;
    for (; end < n1;) {
        end++;    
        sum = sum + a[end] - a[begin++];
        

少了两次 -1计算。由于移动是每个数字都要经历的 这里差不多能节约2n次计算

3、
//printf("移动结果end=%d", end);
        if (a[end] > a[begin - 1]) {
            for (; sum >= S; begin++ ) {
                if ((sum - a[begin]) >= S) {
                    destination[0] = begin + 1;
                    destination[1] = end;
                    sum -= a[begin];
                    //printf("排出一次begin=%d\n", begin);
                }
                else { break; };
改成：

 //printf("移动结果end=%d", end);
            for (; sum - a[begin] >= S;) {
                    destination[0] = begin + 1;
                    destination[1] = end;
                    sum -= a[begin++];
                    //printf("排出一次begin=%d\n", begin);
                };

我发现，其实根本无需管 a[end+1]和a[begin]的大小，直接判断sum-a[begin]和S的大小就结了，只看能否排出即可，少了大量判断。大体上，下坡和上坡各一半，那么少了上坡的两倍判断，基本就少了n次计算了。

gonff

至于错误原因，建议你把数据下下来，先自己试试。主要可以加很多printf来输出当前状态，看看哪里出问题了。
由于小数组不报错，大数组报错。我立刻能想到的原因就是int类型的范围可能不够那么大数据的计数。还有循环是否不允许太长？
如果只是单纯出现了int 不能对付的大数字。那就判断一下，适当情况搬出int32之类的数字类型。
如果是循环不允许太多，那暴力点的办法就是把数据剪切一下，然后再拼接了。  实在不行试试while循环。用for来移动，却只做了一个判断，其实是等于while的。用while似乎就不会出现堆栈溢出了？

gonff

刚刚查了一下，for循环可能会使堆栈溢出。而while循环一般只有死循环，会使内存溢出。所以换成while循环，应该能解决错误问题。

不爱听课的同学

gonff 发表于 2020-11-22 23:57
刚刚查了一下，for循环可能会使堆栈溢出。而while循环一般只有死循环，会使内存溢出。所以换成while循环， ...

我今天去问了一下老师（也是本题的出题人），其实我第一次按你的思路写的代码是正确的，超时的主要原因是没有在输入前一段神秘代码（我也不知道有什么用），但加上后就过了，从300多ms减到了100多ms，代码如下

ios::sync_with_stdio(0);
    cin.tie(0);

最后，十分感谢近来你的耐心解答

gonff

所以是读取耽误了时间？想了那么久的原因。

和你交流我也学到很多，能互相学习，很开心。