找到子阵列，其总和大于钾最小长度 [英] Find minimal length of sub-array whose sum is greater than K

问题描述

我

如何才能找到子阵列排位，其总和大于给定 K ？

我想出了是要保持在指针开始和序列结束，并逐步减去较小的一个缩短序列。但似乎这是无效的。为什么呢？

下面是我的implmentation：

 的#include＆LT;的iostream＆GT;

使用名字空间std;

诠释的main（）{
    而（！cin.eof（））{
        INT caseCount;
        CIN＆GT;＆GT; caseCount;
        INT N，S;
        的for（int i = 0; I＆LT; caseCount;我++）{
            CIN＆GT;＆GT; N'GT;＆GT; S;
            INT * SEQ =新INT [N];
            INT maxSum = 0;
            为（诠释J = 0; J＆所述N; J ++）{
                CIN＆GT;＆GT;以次[J]。
                maxSum + =序列[J]。
            }
            如果（maxSum＆所述S）{
                COUT＆LT;＆LT; 0℃;＆其中; ENDL;
                继续;
            }
            INT左，右;
            左边= 0;
            右= N-1;
            而（左＆LT;右）{
                如果（SEQ [左]＆lt;序列[右]）{
                    如果（maxSum  - 序列[左]＆LT; S）{
                        COUT＆LT;＆LT;左右+ 1＆LT;＆LT; ENDL;
                        打破;
                    } 其他 {
                        maxSum  -  =序列[左]
                        离开++;
                    }
                } 其他 {
                    如果（maxSum  - 序列[右]＆LT; S）{
                        COUT＆LT;＆LT;左右+ 1＆LT;＆LT; ENDL;
                        打破;
                    } 其他 {
                        maxSum  -  =序列[右]
                        对 - ;
                    }
                }
            }
            如果（左＆GT; =右）{
                COUT＆LT;＆LT; 1＆LT;＆LT; ENDL;
            }
        }
    }
    返回0;
}
 

采样输入：

  2 //序列输入量
10 15 //序列1长度和K
5 1 3 5 10 7 4 9 2 8 //序列1数据
5月11日//序列2长度和K
1 2 3 4 5 //序列2数据
 

示例输出：

  2
3
 

解决方案

你的算法不正确。你基本上只检查的顺序，这没有任何意义的中间。相反，你应该从两个指数在阵列的开头和递增右只要子范围的总和大于K.较小当它得到更大的开始递增之前剩余它更小了。现在你有一个候选人的最短子 - 保存。重复，直到右不会得到过去的数组的末尾，更新您的候选人，如果新的更短。

How can I find sub-array qualifying that its sum is greater than a given K?

What I came up with is maintain to pointer at the start and end of the sequence, and incrementally subtract the smaller one to shorten the sequence. But seems it's invalid. Why?

Here is my implmentation:

#include <iostream>

using namespace std;

int main() {
    while (!cin.eof()) {
        int caseCount;
        cin >> caseCount;
        int N, S;
        for (int i = 0; i < caseCount; i++) {
            cin >> N >> S;
            int * seq = new int[N];
            int maxSum = 0;
            for (int j = 0; j < N; j ++) {
                cin >> seq[j];
                maxSum += seq[j];
            }
            if (maxSum < S) {
                cout << 0 << endl;
                continue;
            }
            int left, right;
            left = 0;
            right = N-1;
            while(left < right) {
                if(seq[left] < seq[right]) {
                    if (maxSum - seq[left] < S) {
                        cout << right-left+1 << endl;
                        break;
                    } else {
                        maxSum -= seq[left];
                        left++;
                    }
                } else {
                    if (maxSum - seq[right] < S) {
                        cout << right-left+1 << endl;
                        break;
                    } else {
                        maxSum -= seq[right];
                        right--;
                    }
                }
            }
            if (left >= right) {
                cout << 1 << endl;
            }
        }
    }
    return 0;
}

Sample Input:

2 // amount of sequences to input
10 15 // sequence 1 length and K
5 1 3 5 10 7 4 9 2 8 // sequence 1 data
5 11 // sequence 2 length and K
1 2 3 4 5 // sequence 2 data

Sample Output:

2
3

解决方案

Your algorithm is incorrect. You basically only check middle of the sequence, which doesn't make any sense. Instead you should start with both indexes at the beginning of the array and increment right as long as sum of subrange is smaller than K. When it gets bigger start incrementing left until it is smaller again. Now you have a candidate for your shortest subsequence - save it. Repeat until right won't get past the end of array, updating your candidate if new one is shorter.

这篇关于找到子阵列，其总和大于钾最小长度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！