Pagini recente » Cod sursa (job #2568326) | Cod sursa (job #1659721) | Cod sursa (job #720493) | Cod sursa (job #749253)
Cod sursa(job #749253)
#include <fstream>
#include <iostream>
#include <limits.h>
#include <time.h>
#include <stdio.h>
using namespace std;
typedef struct heapelem{
int key,index;
}heapelem;
//heapelem heap[500001];
int secv[500001];
int baza[500001];
//void heapify(int k,int n)
//{
// while (k<n){
// int l = 2*k+1;
// int r = 2*k+2;
// int max = k;
// if (l<n && heap[l].key<heap[k].key) max = l;
// if (r<n && heap[r].key<heap[max].key) max= r;
// if (max!=k)
// {
// int aux = heap[k].key;
// heap[k].key=heap[max].key;
// heap[max].key=aux;
// aux = heap[k].index;
// heap[k].index=heap[max].index;
// heap[max].index=aux;
// k=max;
// }
// else return;
// }
//}
//void heapifyup(int k)
//{
// while (k>0 && heap[k].key<heap[(k-1)/2].key)
// {
// int max = (k-1)/2;
// int aux = heap[k].key;
// heap[k].key=heap[max].key;
// heap[max].key=aux;
// aux = heap[k].index;
// heap[k].index=heap[max].index;
// heap[max].index=aux;
// k = (k-1)/2;
// }
//}
//heapelem* extractmin(int &n)
//{
// int k=0;
// int max = (n-1);
// int aux = heap[k].key;
// heap[k].key=heap[max].key;
// heap[max].key=aux;
// aux = heap[k].index;
// heap[k].index=heap[max].index;
// heap[max].index=aux;
// n--;
// heapify(0,n);
// return &heap[n];
//}
int main()
{
FILE *f= fopen("secventa.in","r");
int n,k;
fscanf(f,"%d %d",&n,&k);
for (int i=0;i<n;i++)
fscanf(f,"%d",&secv[i]);
fclose(f);
int maxim;
secv[n] = INT_MIN;
int currmin = -1;
baza[n] = INT_MIN;
maxim =n;
for (int i=0;i<n-k+1;i=currmin+1)
{
currmin =i;
for (int j=i+1;j<k+i;j++)
if (secv[j]<secv[currmin])
currmin = j;
baza[i] = secv[currmin];
if (baza[i]>baza[maxim])
maxim = i;
}
/* if (k==1)
{
maxim = secv[0];
for (int i=1;i<n;i++)
if (secv[i]>secv[maxim]) maxim = secv[i];
baza[maxim] = secv[maxim];
}
else{
for (int i=0;i<k;i++)
{
if (secv[i]<secv[i+1]){
heap[heapsize].key=secv[i];
heap[heapsize].index = i;
heapifyup(heapsize);
heapsize++;}
baza[i]=heap[0].key;
}
maxim = k-1;
int i =k;
while (i<n)
{
heap[heapsize].key = secv[i];
heap[heapsize].index = i;
heapifyup(heapsize);
heapsize++;
while (heap[0].index<i-k+1)
{
extractmin(heapsize);
}
baza[i] = secv[i];
if (baza[i]>baza[maxim])
maxim=i;
i = heap[0].index+k;
}
}
*/
ofstream g("secventa.out",ios::out);
g<<maxim+1<<" "<<maxim+k<<" "<<baza[maxim]<<endl;
g.close();
return 0;
}