[Algorytmy] OIG VI - Gumka do mazania

[robek1bobek]

Rozwiązywałem zadanie z VI OIGa - i napisałem je w taki sposob:

Kod: Zaznacz cały

#include<iostream>
#include<string>
#include<vector>
using namespace std;

string lines[ 10000 ] , bitek = "bitek" , wymazany;
int n;

vector< int >poz , poz2;

int ZnajdzLitere( int line , char litera  )
{
    for( int i = poz[ line ] ; i < lines[ line ].size() ; i++ )
    {
        if( lines[ line ][ i ] == litera )
            return i;
    }
    return -1;
}
char ZnajdzNajlepsza()
{
    int j , i , temp;
    for( i = 25 ; i >= 0 ; i-- )
    {
        for( j = 0 ; j < n ; j++ )
        {
            temp = ZnajdzLitere( j , 'a' + i );
            if( temp != -1 )
                poz2[ j ] = temp + 1;

            else
                break;
        }
        if( j == n )
        {
            poz = poz2;
            return i + 'a';
        }
    }
    return -1;
}

int main()
{
    ios_base::sync_with_stdio( 0 );
    bool ok = true , wiekszy = false;
	cin >> n;
	poz.resize( n );
	poz2.resize( n );
	for( int i = 0 ; i < n ; i++ )
        cin >> lines[ i ];

    while( true )
    {
        char temp = ZnajdzNajlepsza();
        if( temp != -1 )
        {
            wymazany += temp;
            if( wymazany.size() <= bitek.size() && !wiekszy )
            {
                if( wymazany[ wymazany.size() - 1 ] < bitek[ wymazany.size() - 1 ] )
                {
                    cout << "bitek";
                    ok = false;
                    break;
                }
                if( wymazany[ wymazany.size() - 1 ] > bitek[ wymazany.size() - 1 ] )
                    wiekszy = true;
            }
        }
        else
            break;
    }
    if( ok )
        cout << wymazany;
	return 0;
}

Problem polega na tym, że rozwiązanie dostaje tylko 70pkt. ( wcale się zresztą temu nie dziwię ).
Wyczytałem na pewnej stronie, że należy zastosować "Malejący ciąg maksimów globalnych". Nie wiem niestety jak to tu wykorzystać. Może ma ktoś jakiś pomysł?

[gryxon]

Sorry, że tak późno.
Problem da rade rozwiązać bardzo prosto w pesymistycznej złożności: \(\displaystyle{ 26n}\), gdzie \(\displaystyle{ n}\) liczba liter na wejściu. Faktyczna złożność będzie jednak o wiele mniejsza .
Zamysł jest prosty. Sprawdzamy litery od \(\displaystyle{ z}\) do \(\displaystyle{ a}\). liczymy minimalną liczbe\(\displaystyle{ (min)}\) wystąpień danej liczby w poszczególnych słowach. Następnie dodajemy literke \(\displaystyle{ min}\) razy do wyniku. Potem oczywiście aktualizujemy słowa ("ucinamy" początki).
Jak już mamy wynik należy porównać go ze słowem "bitek".
Jakbyś miał jakieś wątpliwości lub chciał kod źródłowy to pisz.
Rozwiązanie na mainie przeszło na 100pkt.

[robek1bobek]

Dzięki . Nie śpieszy mi się, przygotowuję się po prostu do finału OIG. Nie pomyślałem, że tak można to napisać. Jak bym miał wątpliwości to napiszę .

[janek880]

Hej.zastosowałem się do wskazówek,jednak mam jakiś bład którergo nie mogę znaleźć i mam 10 p.Czy mógłby mi ktoś pomóc.oto kod:

Kod: Zaznacz cały

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string tab[100000];
int liczba[26];
void funkcja(string s)
{
  for(int i=0;i<=25;++i)
  {
          int ile=0;
          char c=i+97;
          int dl=s.size();
          for(int q=0;q<dl;q++)
          {
                  if(s[q]==c)
                  {
                             ile++;           
                  }        
          }  
          if(ile<liczba[i])
          {
                              liczba[i]=ile;                    
          }      
  } 
   
}
int main()
{
    int n;
    cin>>n;
    string s;
    string b="bitek";
    string wynik="";
    string pom="";
    for(int i=0;i<=26;++i)
    {
        liczba[i]=999999999;    
    }
    for(int i=0;i<n;++i)
    {
            cin>>s;
             funkcja(s); 
    }
    int dl=s.size();
    for(int i=0;i<dl;++i)
    {
            int q=s[i]-97;
            if(liczba[q]>0)
            {
                        liczba[q]--;
                        pom=pom+s[i];
                                    
            }        
            
    }
    int pomd=pom.size();
    
    for(int i=0;i<pomd;++i)
    {
            bool czy=false;
            for(int q=i+1;q<pomd;++q)
            {
                    if(pom[q]>pom[i])
                    {
                                     czy=true;
                       break;              
                    }        
            }        
    if(czy==false)
    {
                  wynik=wynik+pom[i];              
    }
    }
    if(wynik<b)
    {
               cout<<"bitek";           
    }
    else
    {
    for(int i=0;i<wynik.size();i++)
    {
            cout<<wynik[i];        
    }
}
    cout<<endl;
system("pause");
 return 0;   
}