[已解决]复杂循环数组

不爱听课的同学

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


难度升级


代码长度限制
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

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

1. #include <stdio.h>
   
2. 
   
3. //用指针比较方便返回数组
   
4. int * find(int n, int S, int a[]) {
   
5.         //初始化盒子参量
   
6.         int begin = 0;
   
7.         int end = 0;
   
8.         int sum = a[0];
   
9. 
   
10.         int destination[3] = { 0, 0, 0 };//最终返回的数组：第一二分量是盒子的开头和结尾，第三分量标记是否溢出。
    
11. 
    
12.         //开始吞入：
    
13.         for (; sum < S;) {
    
14.                 if (end < n-1) {
    
15.                         end++;
    
16.                         sum += a[end];
    
17.                 }
    
18.                 else { destination[2] = -1; break; };
    
19.         };
    
20.         //printf("吞入完成后end=%d\n", end);
    
21. 
    
22.         //开始排出；
    
23.         for (; sum >= S; begin++) {
    
24.                 if (sum - a[begin] >= S) {
    
25.                         destination[0] = begin+1;
    
26.                         destination[1] = end;
    
27.                         sum -= a[begin];
    
28.                         //printf("排出一次begin=%d\n", begin);
    
29.                 }
    
30.                 else { break; };
    
31.         };
    
32. 
    
33.         //printf("本次排出后begin=%d\tend=%d\n", begin,end);
    
34. 
    
35.        
    
36.         //开始移动判断的循环
    
37.         for (; end < n-1;) {
    
38.                 sum = sum + a[end + 1] - a[begin];
    
39.                 end++;
    
40.                 begin++;
    
41.                 //printf("移动结果end=%d", end);
    
42.                 if (a[end] > a[begin - 1]) {
    
43.                         for (; sum >= S; begin++) {
    
44.                                 if ((sum - a[begin]) >= S) {
    
45.                                         destination[0] = begin+1;
    
46.                                         destination[1] = end;
    
47.                                         sum -= a[begin];
    
48.                                         //printf("排出一次begin=%d\n", begin);
    
49.                                 }
    
50.                                 else { break; };
    
51.                         };
    
52.                 };
    
53.         };
    
54.         return destination;
    
55. }
    
56. 
    
57. void main() {
    
58.         //初始化数据
    
59.         int n = 9;
    
60.         int S = 15;
    
61.         int a[] = { 1, 1, 3, 5, 10, 13, 19, 19, 5};
    
62.         int sizea;
    
63.         sizea = sizeof(a) / sizeof(int);
    
64.         if (n != sizea) {
    
65.                 printf("尺寸不对，已改正n=%d\n", sizea);
    
66.                 n = sizea;
    
67.         };
    
68. 
    
69. 
    
70.         //指针用于返回数组
    
71.         int *p;
    
72.         p = find(n, S, a);
    
73.         if (*(p+2) == -1) {
    
74.                 printf("%d\n", 0); printf("%d\n", 0);
    
75.         }
    
76.         else {
    
77.                 int destination[2] = { 0, 0 };
    
78.                 destination[0] = *p;
    
79.                 destination[1] = *(p + 1);
    
80.                 //printf("destination[0]=%d\n", destination[0]);
    
81.                 //printf("destination[1]=%d\n", destination[1]);
    
82.                 int len;
    
83.                 len = destination[1] - destination[0] + 1;
    
84. 
    
85.                 //打印结果
    
86.                 int i = 0;
    
87.                 printf("%d\n", len);
    
88.                 if (len > 1) {
    
89.                         for (; i < len - 1; i++) {
    
90.                                 printf("%d", a[destination[0] + i]);
    
91.                         };
    
92.                 }
    
93.                 else { printf("%d", a[destination[0]]); };
    
94.         };
    
95. }

复制代码

不爱听课的同学

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

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

1. #include <iostream>
   
2. using namespace std;
   
3. int num[50][1000000];
   
4. int main()
   
5. {
   
6.         int N, lens[50][2], begin = 0, end = 0, sum, Begin, End;   //lens[50][2]储存数组长度和整数S  Begin和End存储起始点和结尾点
   
7.         cin >> N;
   
8.         for (int i = 1;i <= N;i++) {         //数组录入      
   
9.                 cin >> lens[i][0] >> lens[i][1];
   
10.                 for (int j = 0;j < lens[i][0];j++) cin >> num[i][j];
    
11.         }
    
12. 
    
13.         int len, S;
    
14.         for (int i = 1;i <= N;i++) {   
    
15.                 len = lens[i][0];S = lens[i][1];
    
16.                 begin = 0;end = 0;sum = 0;
    
17.                 Begin = 0;End = 0;
    
18.                 for (int j = 0;sum < S && j < len;j++) {      //吞入数字
    
19.                         sum += num[i][j];
    
20.                         end = j;
    
21.                 }
    
22. 
    
23.                 if (sum < S) {         //判断是否存在大于整数S的序列
    
24.                         cout << 0 << endl << 0;
    
25.                         if (i != N) cout << endl;
    
26.                         continue;
    
27.                 }
    
28. 
    
29.                 while (1) {           //移出数字
    
30.                         if ((sum - num[i][begin]) >= S) {
    
31.                                 sum -= num[i][begin];
    
32.                                 begin++;
    
33.                         }
    
34.                         else break;
    
35.                 }
    
36.                 Begin = begin;End = end;
    
37. 
    
38.                 while (begin < len - 1) {
    
39.                         begin++;end++;                        //右移盒子
    
40.                         sum -= num[i][begin - 1];sum += num[i][end];
    
41. 
    
42.                         if (sum >= S) {
    
43.                                 if (num[i][end] > num[i][begin - 1]) {     //若新加入的数字比移除的数字更大
    
44.                                         while (1) {
    
45.                                                 if ((sum - num[i][begin]) >= S) {  //判断是否可以移除数字
    
46.                                                         sum -= num[i][begin];
    
47.                                                         begin++;
    
48.                                                         Begin = begin;End = end;
    
49.                                                 }
    
50.                                                 else break;
    
51.                                         }
    
52.                                 }
    
53.                         }
    
54.                 }
    
55. 
    
56.                 cout << End - Begin + 1 << endl;     //输出结果
    
57.                 for (int j = Begin;j <= End;j++) {
    
58.                         cout << num[i][j];
    
59.                         if (j == End) cout << endl;
    
60.                         else cout << ' ';
    
61.                 }
    
62.         }
    
63.         return 0;
    
64. }

复制代码

gonff

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

不爱听课的同学

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

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

修改后的代码如下

1. #include <iostream>
   
2. using namespace std;
   
3. int num[50][1000000];
   
4. //用指针比较方便返回数组
   
5. int* find(int n, int S, int a[]) {
   
6.     //初始化盒子参量
   
7.     int begin = 0;
   
8.     int end = 0;
   
9.     int sum = a[0];
   
10. 
    
11.     int destination[3] = { 0, 0, 0 };//最终返回的数组：第一二分量是盒子的开头和结尾，第三分量标记是否溢出。
    
12. 
    
13.     //开始吞入：
    
14.     for (; sum < S;) {
    
15.         if (end < n - 1) {
    
16.             end++;
    
17.             sum += a[end];
    
18.         }
    
19.         else { destination[2] = -1; break; };
    
20.     };
    
21.     //printf("吞入完成后end=%d\n", end);
    
22. 
    
23.     //开始排出；
    
24.     for (; sum >= S; begin++) {
    
25.         if (sum - a[begin] >= S) {
    
26.             destination[0] = begin + 1;
    
27.             destination[1] = end;
    
28.             sum -= a[begin];
    
29.             //printf("排出一次begin=%d\n", begin);
    
30.         }
    
31.         else { break; };
    
32.     };
    
33. 
    
34.     //printf("本次排出后begin=%d\tend=%d\n", begin,end);
    
35. 
    
36. 
    
37.     //开始移动判断的循环
    
38.     for (; end < n - 1;) {
    
39.         sum = sum + a[end + 1] - a[begin];
    
40.         end++;
    
41.         begin++;
    
42.         //printf("移动结果end=%d", end);
    
43.         if (a[end] > a[begin - 1]) {
    
44.             for (; sum >= S; begin++) {
    
45.                 if ((sum - a[begin]) >= S) {
    
46.                     destination[0] = begin + 1;
    
47.                     destination[1] = end;
    
48.                     sum -= a[begin];
    
49.                     //printf("排出一次begin=%d\n", begin);
    
50.                 }
    
51.                 else { break; };
    
52.             };
    
53.         };
    
54.     };
    
55.     return destination;
    
56. }
    
57. 
    
58. int main() {
    
59.     //初始化数据
    
60.     int N, lens[50][2];   //lens[50][2]储存数组长度和整数S
    
61.     cin >> N;
    
62.     for (int i = 1;i <= N;i++) {         //数组录入
    
63.         cin >> lens[i][0] >> lens[i][1];
    
64.         for (int j = 0;j < lens[i][0];j++) cin >> num[i][j];
    
65.     }
    
66. 
    
67.     int n, S;
    
68.     for (int i = 1;i <= N;i++) {
    
69.         n = lens[i][0];S = lens[i][1];
    
70.         int* p;
    
71.         p = find(n, S, num[i]);
    
72.         if (*(p + 2) == -1) {
    
73.             cout << 0 << endl << 0 << endl;
    
74.         }
    
75.         else {
    
76.             int destination[2] = { 0, 0 };
    
77.             destination[0] = *p;
    
78.             destination[1] = *(p + 1);
    
79.             //printf("destination[0]=%d\n", destination[0]);
    
80.             //printf("destination[1]=%d\n", destination[1]);
    
81.             int len;
    
82.             len = destination[1] - destination[0] + 1;
    
83.             //打印结果
    
84.             cout << len << endl;
    
85.             for (int j = destination[0];j <= destination[1];j++) {
    
86.                 cout << num[i][j];
    
87.                 if (j == destination[1]) cout << endl;
    
88.                 else cout << ' ';
    
89.             }
    
90.         }
    
91.     }
    
92.     return 0;
    
93. }

复制代码

赚小钱

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

过，下一题。

gonff

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

1.     //开始排出；
   
2.     for (; sum >= S; begin++) {
   
3.         if (sum - a[begin] >= S) {
   
4.             destination[0] = begin + 1;
   
5.             destination[1] = end;
   
6.             sum -= a[begin];
   
7.             //printf("排出一次begin=%d\n", begin);
   
8.         }
   
9.         else { break; };
   
10.     };

复制代码

改成:

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

复制代码

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

2、

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

复制代码

改成

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

复制代码

少了两次 -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; };
改成：

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

复制代码

我发现，其实根本无需管 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，代码如下

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

复制代码

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

gonff

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

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