Pagini recente » Cod sursa (job #1606524) | Cod sursa (job #161182) | Cod sursa (job #113561) | Cod sursa (job #1181130) | Cod sursa (job #716281)
Cod sursa(job #716281)
#include<fstream>
#include<iostream>
using namespace std;
struct deque
{
int n;
int* elems;
};
/*
* Create a deque
*/
void create(deque& a, int n)
{
// for (int i = 1; i<=n; i++)
// a.elems[i] = new int;
}
/*
* Append element to end of deque
*/
void append(deque& a, int el)
{
a.n ++;
a.elems[a.n] = el;
}
/*
* Remove element from beginning of deque
*/
void removeFirst(deque& a)
{
for (int i = 1; i<= a.n; i++)
a.elems[i-1] = a.elems[i];
a.n --;
}
/*
* Remove last element from deque
*/
void removeLast(deque& a)
{
a.n --;
}
/*
* Add element to beginning of deque
*/
void appendFirst(deque& a, int el)
{
a.n++;
for(int i = a.n; i>1; i--)
a.elems[i] = a.elems[i-1];
a.elems[1] = el;
}
int getMin(deque a, int length)
{
int min = 30001;
for (int i = 1; i<= length; i++)
if (a.elems[i] < min)
min = a.elems[i];
return min;
}
int main()
{
int n, k, min = -30001, tmpMin;
deque a;
int sPos, fPos;
int turns, length;
ifstream inFile;
ofstream outFile;
inFile.open("secventa.in");
inFile>>n;
inFile>>k;
a.n = n;
a.elems = new int[n];
for (int i = 1; i<=n; i++)
inFile>>a.elems[i];
length = n; // initialize max length with length of deque
turns = n - length ; // initialize turns with difference between n and length
while(length >= k) // while the length of the deque is greater than the minimum length
{
tmpMin = getMin(a, length); // get the minimum in the sequence with the given length
if (tmpMin > min) // if temporary minimum is greater than the overall minimum, save min and sequence properties
{
sPos = 1 + n - (length + turns);
fPos = sPos + length - 1;
min = tmpMin;
}
if (turns > 0)
{
int aux = a.elems[1];
removeFirst(a);
append(a, aux);
turns --;
}
else
{
length--; // search for shorter sequence
turns = n - length; // more turns than before
int aux = turns - 1;
while(aux > 0) // restore deque
{
int tmp = a.elems[a.n];
removeLast(a);
appendFirst(a, tmp);
aux --;
}
}
}
inFile.close();
outFile.open("secventa.out");
outFile<<sPos<<" "<<fPos<<" "<<min;
outFile.close();
return 0;
}