复杂循环数组,C\C++交流,技术交流,鱼C论坛

不爱听课的同学 发表于 2020-11-20 16:30:43

复杂循环数组

本帖最后由不爱听课的同学于 2020-11-20 18:21 编辑

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

难度升级

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

Cool_Breeze 发表于 2020-11-20 17:19:03

抱歉，我连题都没有看懂题！{:10_266:}

不爱听课的同学 发表于 2020-11-20 18:22:29

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

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

gonff 发表于 2020-11-21 02:27:17

本帖最后由 gonff 于 2020-11-21 03:07 编辑

我的想法：
设置一个盒子，可以加入和排出序列。其关键因素是头（begin），尾（end）位置，以及二者之间元素的和（sum）。
盒子有两个基本能力：
排出数字：其实就是特殊的移动，sum=sum-a;begin+=1;
吞入数字：sum=sum+a;end+=1;
二者组合可以变成“移动”：sum=sum+a-a;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-a;begin+=1;end+=1;加法记得是一步步加的，所以3个式子实际计算了4次。
总之这个思路下，所有行为都是O(n）的。总的来说也就应该是O(n)的。

gonff 发表于 2020-11-21 03:15:30

比如你给的第一个输入，我来描述一下：
首先吞入前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]也就是

gonff 发表于 2020-11-21 12:30:22

本帖最后由 gonff 于 2020-11-21 13:03 编辑

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

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

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

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

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

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

//开始移动判断的循环
for (; end < n-1;) {
sum = sum + a - a;
end++;
begin++;
//printf("移动结果end=%d", end);
if (a > a) {
for (; sum >= S; begin++) {
if ((sum - a) >= S) {
destination = begin+1;
destination = end;
sum -= a;
//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 = { 0, 0 };
destination = *p;
destination = *(p + 1);
//printf("destination=%d\n", destination);
//printf("destination=%d\n", destination);
int len;
len = destination - destination + 1;

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

不爱听课的同学 发表于 2020-11-21 20:44:10

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;
int main()
{
int N, lens, begin = 0, end = 0, sum, Begin, End; //lens储存数组长度和整数SBegin和End存储起始点和结尾点
cin >> N;
for (int i = 1;i <= N;i++) {       //数组录入
cin >> lens >> lens;
for (int j = 0;j < lens;j++) cin >> num;
}

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

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

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

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

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

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

gonff 发表于 2020-11-21 22:48:56

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

不爱听课的同学 发表于 2020-11-22 11:06:03

本帖最后由不爱听课的同学于 2020-11-22 11:07 编辑

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

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

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

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

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

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

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

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

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

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

赚小钱 发表于 2020-11-22 21:25:54

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

过，下一题。

gonff 发表于 2020-11-22 23:25:25

本帖最后由 gonff 于 2020-11-23 10:58 编辑

找到几个可以改进的点。
1、
//开始排出；
for (; sum >= S; begin++) {
   if (sum - a >= S) {
         destination = begin + 1;
         destination = end;
         sum -= a;
         //printf("排出一次begin=%d\n", begin);
   }
   else { break; };
};

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

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

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

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

3、
//printf("移动结果end=%d", end);
   if (a > a) {
         for (; sum >= S; begin++ ) {
            if ((sum - a) >= S) {
               destination = begin + 1;
               destination = end;
               sum -= a;
               //printf("排出一次begin=%d\n", begin);
            }
            else { break; };
改成： //printf("移动结果end=%d", end);
         for (; sum - a >= S;) {
               destination = begin + 1;
               destination = end;
               sum -= a;
               //printf("排出一次begin=%d\n", begin);
            };
我发现，其实根本无需管 a和a的大小，直接判断sum-a和S的大小就结了，只看能否排出即可，少了大量判断。大体上，下坡和上坡各一半，那么少了上坡的两倍判断，基本就少了n次计算了。

gonff 发表于 2020-11-22 23:39:53

本帖最后由 gonff 于 2020-11-22 23:55 编辑

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

gonff 发表于 2020-11-22 23:57:22

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

不爱听课的同学 发表于 2020-11-23 23:24:31

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

我今天去问了一下老师（也是本题的出题人），其实我第一次按你的思路写的代码是正确的，超时的主要原因是没有在输入前一段神秘代码（我也不知道有什么用），但加上后就过了，从300多ms减到了100多ms，代码如下
ios::sync_with_stdio(0);
cin.tie(0);
最后，十分感谢近来你的耐心解答

gonff 发表于 2020-11-23 23:40:27

所以是读取耽误了时间？想了那么久的原因。{:9_226:}

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

页: [1]

鱼C论坛's Archiver

复杂循环数组