-4

その合計が指定されたより大きいことを修飾する部分配列を見つけるにはどうすればよいKですか?

私が思いついたのは、シーケンスの開始と終了でポインターを維持し、小さい方を段階的に減算してシーケンスを短縮することです。しかし、それは無効のようです。なんで？

これが私の実装です：

#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;
}

サンプル入力:

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

サンプル出力:

2
3
4

4 に答える 4

1

これはPythonのアイデアです（ほとんどがアルゴリズムの問​​題であるため）、入力が自然数であると仮定します（@ChrisOkasakiに感謝します）。s で動作しlistますが、目的に合わせて簡単に調整できるはずです。startとの両方endが含まれます。サブ配列の最初と最後のインデックスの両方を返します。

def find_minimal_length_subarr(arr, min_sum):
    found = False
    start = end = cur_start = cur_end = 0
    cur_sum = arr[cur_start]
    while cur_end < len(arr):
        if cur_start < cur_end:
            cur_sum += arr[cur_end]
        while cur_sum-arr[cur_start] >= min_sum:
            cur_sum -= arr[cur_start]
            cur_start += 1
        if cur_sum >= min_sum and (not found or cur_end-cur_start < end-start):
            start, end = cur_start, cur_end
            found = True
        cur_end += 1
    if found:
        return start, end

print find_minimal_length_subarr([11, 2, 3, 4, 9, 5, 6, 7, 8], 21) # (6, 8)

最初から開始し、min_sum到達しない間は右に拡張します。min_sum達すると、まだ達している間に左から短くなります。その後、再び拡大を続けます。より良い (より短い) 候補が見つかった場合にのみ、以前の候補が置き換えられます。時間の計算量は O(n)、空間の計算量は O(1) です。

于 2013-06-29T10:56:58.750 に答える
1

これは、Thijs アルゴリズムに基づく C++ での作業例です。これは、問題の理想的なアルゴリズムのように見えます (正しく理解されている場合。述語に一致する最初のサブシーケンスまたはすべてのサブシーケンスを見つけるために簡単に変更できます)。

#include <vector>
#include <utility>
#include <iostream>

using namespace std;
template<typename It>
pair<It, It> subseq_with_sum_greater(It begin, It end, typename It::value_type barrier)
{
    typename It::value_type current_sum = 0;
    pair<It, It> res = make_pair(begin, end);
    for(It current = begin; current < end; ++current)
    {
        current_sum += *current;
        while(current_sum > barrier and current_sum - *begin > barrier)
            current_sum -= *begin++;
        if(current_sum > barrier and distance(begin, current) < distance(res.first, res.second))
            res = make_pair(begin, current);
    }
    return res;
}

int main()
{
    vector<int> v = {5, 1, 3, 5, 10, 7, 4, 9, 2, 8};
    auto subseq = subseq_with_sum_greater(v.begin(), v.end(), 15);
    cout << distance(v.begin(), subseq.first) << ", " << distance(v.begin(), subseq.second);
}

出力は4, 5、サブシーケンスのインデックスです。std::distance使用は RandomAccess イテレータ (std::vector のイテレータなど) でのみ O(1) の複雑さであることに注意してくださいsize_t current_distance, minimal_distance。この種のテンプレートを他のコンテナで使用する場合は、変数を追加することをお勧めします。また、サブシーケンスが見つからない場合、このアルゴリズムはbegin, endペアを返すため、これが答えなのか、サブシーケンスが一致しないのかを判断するのが難しくなります。ケースによっては、より正確な出力が必要になる場合があります。

于 2013-06-29T11:53:21.750 に答える
0

あなたのアルゴリズムは正しくありません。基本的にシーケンスの途中だけをチェックしますが、これは意味がありません。代わりに、配列の先頭にある両方のインデックスから開始し、サブ範囲の合計が K より小さい限り右にインクリメントする必要があります。それが大きくなると、再び小さくなるまで左にインクリメントし始めます。これで、最短のサブシーケンスの候補ができました - それを保存します。右が配列の終わりを超えなくなるまで繰り返し、新しい候補が短い場合は候補を更新します。

于 2013-06-29T10:56:30.010 に答える