Imprimă pagina - 304 Sirag

Ok, pai eu am rezolvat problema folosind heap-uri. Creez un max-heap si la fiecare pas extrag p maxime, scad minimul din toate si le reintroduc in heap. Iar numarul de siruri formate la fiecae pas p*min, apoi la final adun numaul de element ramase in heap. Problema este ca nu inteleg de ce pic pe al doilea test, daca puteti sa-mi spuneti unde gresesc ?

Cod:

#include <fstream>
#include <iterator>
#define Nmax 100001

/*
 *
 */
 using namespace std;
 int N;
 int H[Nmax], v[Nmax];
 void DownHeap( int k )
 {
     int son;
     while( true )
     {
         son=2*k;
         if( son > N )
            return;
         if( son < N && H[son] < H[son+1] )
            ++son;
         if( H[k] >= H[son] )
            return;
         swap( H[k], H[son] );
         k=son;
     }
 }
 void UpHeap( int k )
 {
     int key=H[k], f=k/2;
     while( k > 1 && key > H[f] )
     {
         swap( H[k], H[f] );
         k=f;
         f/=2;
     }
 }
int main( void )
{
    int k, i, j;
    ifstream in("sirag.in");
    in>>N>>k;
    copy( istream_iterator<int>( in ), istream_iterator<int>(), H+1 );
    for( i=N/2; i > 0; --i )
        DownHeap( i );
    for( j=0; N >= k; j+=k*v[k]  )
    {
        for( i=1; i <= k; ++i )
        {
            v[i]=H[1];
            H[1]=H[N];
            --N;
            DownHeap( 1 );
        }
        for( i=1; i < k; ++i )
        {
            v[i]-=v[k];
            if( v[i] > 0 )
            {
                H[++N]=v[i];
                UpHeap( N );
            }
        }
    }
    j+=N;
    ofstream out("sirag.out");
    out<<j<<'\n';
    return 0;
}

Citat din mesajul lui: Andrei Grigorean din Februarie 12, 2010, 17:12:05

algoritmul in schimb este prost. Pentru exemplul:

Multumesc pentru exemplu :). Chiar acuma am facut rost de descrierea solutie si am citit ca ei fac la fel ca mine sau n-am inteles eu bine ?

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Adrian Diaconu din Martie 28, 2009, 13:42:50