Cod sursa(job #749175)

Utilizator iris88Nagy Aliz iris88 Data 15 mai 2012 23:31:02
Problema Secventa Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <fstream>
#include <iostream>
using namespace std;
typedef struct heapelem{
  int key,index;
}heapelem;

heapelem *heap;
int *secv;
int *baza;
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)
      if (heap[l].key<heap[k].key) max = l;
    if (r<n)
      if (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=aux;
    }
    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()
{
  ifstream f("secventa.in",ios::in);
  int n,k;
  f>>n>>k;
  secv = new int[n];
  heap = new heapelem[n];
  baza = new int[n];
  for (int i=0;i<n;i++)
    f>>secv[i];
  int heapsize = 0;
  f.close();
  for (int i=0;i<k;i++)
  {
    heap[heapsize].key=secv[i];
    heap[heapsize].index = i;
    heapifyup(heapsize);
    heapsize++;
    baza[i]=heap[0].key;
  }
  for (int i=k;i<n;i++)
  {
    heap[heapsize].key = secv[i];
    heap[heapsize].index = i;
    heapifyup(heapsize);
    heapsize++;
    while (heap[0].index<i-k+1)
    {
      extractmin(heapsize);
    }
    baza[i] = heap[0].key;
  }
  int maxim = k-1;
  for (int i=k;i<n;i++)
  {
    if (baza[i]>baza[maxim])
      maxim=i;
  }
  ofstream g("secventa.out",ios::out);
  g<<maxim-k+2<<" "<<maxim+1<<" "<<baza[maxim]<<endl;
  g.close();
  return 0;
}