Pagini recente » Cod sursa (job #1949503) | Cod sursa (job #1770917) | Cod sursa (job #719746)
Cod sursa(job #719746)
#include <fstream>
#include <iostream>
using namespace std;
int min(int w[], int &lmp, int nmp)
{
int m=w[lmp];
if(m>w[nmp])
{
m=w[nmp];
lmp=nmp;
}
return m;
}
int main()
{
int n, k, c=1 ,p=0, poz=0, lmp=0;
int base=-30001,b=-30001, a[500001];
fstream f("secventa.in",ios::in);
f>>n>>k;
for (int i=0;i<n ;i++)
{
f>>a[i];
}
f.close();
for (int i=0;i<n ;i++)
{
// cout<<"b="<<b<<"\n";
// cout<<"p="<<p<<"\n";
// cout<<"c="<<c<<"\n";
if ((c==k)&&(base<b))//daca baza(base) maxima e mai mica decat cea curenta(b)
{
base=b; //avem o noua baza maxima
poz=p; //cu o secventa care incepe de la pozitia p
// cout<<"base<b =>\n";
// cout<<"base="<<base<<"\n";
// cout<<"poz="<<poz<<"\n";
}
if (b>a[i]) //daca baza curenta e mai mare decat a[i]
{
p=i; //pornim o alta secventa de la poz i
c=1; //cu lungimea c
lmp=i; //si noul last min position(lmp) este i
// cout<<"b>a[i] =>\n";
// cout<<"p="<<p<<"\n";
// cout<<"c="<<c<<"\n";
}
else
{
if(c<k) //daca "fereasta" secventei nu e inca de lungimea necesara
{
c++; //o marim cu o pozitie
b=min(a,lmp,p+c-1); //si verificam daca elementul de pe noua pozitie e baza
//cout<<"c++ => c="<<c<<"\n";
}
else //daca totusi c-ul a ajuns la k
{
p++; //atunci mutam fereasta cu totul o pozitie
if (lmp==p-1) //daca minimul (baza) secv era pe prima pozitie
{
lmp=p; //la mutarea ferestri l-am pierdut si cautam noul minim(baza) a secv
for (int j=p+1; j<p+c; j++)
{
if (a[j]<a[lmp])
lmp=j;
}
}
b=a[lmp]; //avem noua baza
// cout<<"p++ => p="<<p<<"\n";
//c--;
}
}
}
b=min(a,lmp,p+c-1); //verificam si dupa ultima iteratie daca nu cumva am gasit o alt secv convenabila
if ((c==k)&&(base<b))
{
base=b;
poz=p;
// cout<<"base<b =>\n";
// cout<<"base="<<base<<"\n";
// cout<<"poz="<<poz<<"\n";
}
while ((a[poz-1]==base)||(a[poz+k]==base))
{
if (a[poz-1]==base)
{
poz--;
k++;
}
if (a[poz+k]==base)
{
k++;
}
}
fstream g("secventa.out",ios::out);
g<<poz+1<<" "<<poz+k<<" "<<base;
cout<<poz+1<<" "<<poz+k<<" "<<base;
g.close();
return(0);
}