Блог

Я ищу способ поиска минимального последующего размера из последовательности, сумма которой удовлетворяет минимальной сумме, необходимой из вопроса.
Примеры (обратите внимание, что индекс начинается с 0):

 arr[]={5, 1, 3, 5, 10, 7, 4, 9, 2, 8}  
sum = 15  
  

итак, ответ должен быть 2, потому что минимальный размер подпоследовательности равен от

 a[3]-a[4].  
arr[]={1, 2, 3, 4, 5}  
sum = 11  
  

итак, ответ должен быть 3, потому что минимальный размер подпоследовательности равен от

 a[2]-a[4].  
  

Я попытался использовать жадный метод с кодом ниже:

 #include <bits/stdc  .h>
using namespace std;
int main(){
    vector <int> sequence;

    int sequenceSize, sumAsked;
    cin>>sequenceSize>>sumAsked;
    
    int sum=0, count=sequenceSize, front=0, back=sequenceSize-1;

    for(int i=0; i<sequenceSize; i  ){
        int j;
        cin>>j;
        sequence.push_back(j);
        sum =j;
    }
    if(sum<sumAsked){
        cout<<0<<endl;
    }
    else{
        while(sum>sumAsked){
            if(sequence[front]>=sequence[back]){
                sum-=sequence[back];
                back--;
                count--;
            }
            else{
                sum-=sequence[front];
                front  ;
                count--;
            }
        }
    cout<<count 1<<endl;
    }
}
  

Код, похоже, работает в обоих тестовых примерах, но он ошибся в онлайн-оценке. Есть ли лучший код или метод для меня, с которым я могу работать?

Я действительно получил accepted ответ на судью, и он выглядел так,

 #include <bits/stdc  .h>
#define f first
#define s second

typedef long long int lli;
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int sequenceSize, sumAsked, sum=0;
    cin>>sequenceSize>>sumAsked;
    vector <int> sequence;
    for(int i=0; i<sequenceSize; i  ){
        int j;
        cin>>j;
        sequence.push_back(j);
        sum =j;
    }
    if(sum<sumAsked) cout<<0<<endl; //whether to check it's possible or not to get the answer,
    else{                           //otherwise it prints 0
        vector <int> note;
        int currentPos=0, currentSum=0, count=0;
        int temp=sequence[currentPos];
        for(int i=0; i<sequenceSize; i  ){
            currentSum =sequence[i];    //here we add the sum one by one from the sequence
            count  ;
            while(!(currentSum-temp<sumAsked)){ //here we reduce the size of the 'window'
                currentSum-=temp;               //until it's just enough to hold the sum
                count--;
                cur  ;
                temp=sequence[cur];
                note.push_back(count); //to take note all possible 'window' size
            }
        }
        for(int i=0; i<note.size(); i  ){
            count=min(count, note[i]); //to search the best possible minimum answer
        }
        cout<<count<<endl;
    }
    return 0;
}
  

Я думаю, что возможно, однако, не принимать во внимание весь ответ по вектору, но я думаю, что это уже достаточно хорошо.