Cerinţa

Se dă un şir de n numere întregi şi un număr k. Să se determine intervalul [a,b] de lungime minimă care conţine cel puţin k elemente din sir.

Date de intrare

Fişierul de intrare interval1.in conţine pe prima linie numerele n şi k, iar pe următoarele linii n numere întregi separate prin spaţii, reprezentând elementele şirului.

Date de ieşire

Fişierul de ieşire interval1.out va conţine pe prima linie două numere a şi b, separate printr-un spaţiu, cu semnificaţia de mai sus.

Restricţii şi precizări

1 ≤ k ≤ n ≤ 1000
elementele şirului aparţin intervalului [-1000,1000] şi pot fi dispuse în fişierul de intrare pe mai multe linii
dacă există mai multe intervale [a,b] de lungime minimă care conţin cel puţin k elemente din sir se va alege acela pentru care a este minim
a ≤ b

Exemplu

interval1.in

10 3
11 9 3 2 8 11 9 10 15 13

interval1.out

8 9

Explicație

Intervalul [8,9] conţine 3 elemente ale şirului – 8 9 9 şi are lungimea minimă. Există încă un interval cu aceeaşi lungime care conţine 3 elemente din şir – [9,10] elemente dar 8<9.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Interval1:

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

ifstream fin("interval1.in");
ofstream fout("interval1.out");

int n, k, a[1005];

int main(){
    fin >> n >> k;
    for(int i=1;i<=n;++i)
        fin >> a[i];
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
                if(a[i]>a[j]){
                    int aux = a[i];
                    a[i] = a[j];
                    a[j] = aux;
                }
    int aa=a[1],bb=a[k];
    for(int i=1;i<=n-k+1;++i)
        if(a[i+k-1]-a[i]<bb-aa)
            aa = a[i], bb = a[i+k-1];
    fout << aa << " " << bb;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #184 Interval1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #184 Interval1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #184 Interval1