Cod sursa(job #719746)

Utilizator m_mihai92Mocanu Mihai m_mihai92 Data 22 martie 2012 00:07:28
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#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);
}