Zadanie wieża problrm

Question

Witam mam problem z zadanie wieża http://main.edu.pl/pl/archive/ilocamp/2010/wie nie wim jak sie uporać ze powtórzeniami np nie działa dla przykładu 3 1 4 4 4 5 i wypisuje 2 i nie wiem jak to naprawić bo  od razu znajduje ta liczbę i nie wiem jak zrobić żeby sprawdziło jeszcze następne  jeś dziękuje za każdą pomoc:)
 

#include <iostream>
using namespace std;
int tab[1000000],tab2[1000000],to[1000000];
int szukana(int poc,int kon,int x)
{
    int sr;
    while(poc<=kon)
    {
        sr=(poc+kon)/2;
        if(to[sr]<x)
        {
            poc=sr+1;
            x=sr+1;
            return x;

        }
        else
            kon=sr-1;
    }
}

int main ()
{
    ios_base::sync_with_stdio(0);
    int n,m,x;
    cin>>n>>m;
    for(int i=0; i<n; i++)
        cin>>tab[i];
    to[0]=tab[0];
    for(int i=0; i<m; i++)
        cin>>tab2[i];
    for(int i=1; i<n; i++)
        to[i]=max(to[i-1],tab[i]);
    for(int i=0; i<m; i++)
    {

        cout<<szukana(0,n-1,tab2[i])<<" ";

    }
}

Comments

Kod na forum wstawiamy w przeznaczony do tego bloczek, pamiętaj na przyszłość.

---

Użycie std::upper_bound jest przyjemniejsze i prostsze niż pisanie własnej funkcji szukającej. Po co pisać coś, co ktoś napisał dla Ciebie i jest w dodatku w bibliotece standardowej ?

#include <algorithm>
#include <iostream>
#include <vector>

int main(void) {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);

    int height, n, m;
    std::cin >> n >> m;

    std::vector<int> stairs(n);
    std::cin >> stairs[0];
    for(int i = 1; i < stairs.size(); ++i) {
        std::cin >> stairs[i];
        stairs[i] = std::max(stairs[i-1], stairs[i]);
    }

    while(m--) {
        std::cin >> height;
        int index = std::upper_bound(stairs.rbegin(), stairs.rend(), height, std::greater<int>()) - stairs.rbegin();
        std::cout << stairs.size() - index << " ";
    }
    std::cout << std::endl;
    return 0;
}

 

Answer 1

int szukana(int poc,int kon,int x)
{
    int sr;
    while(poc<=kon)
    {
        sr=(poc+kon)/2;
        if(to[sr]<x)
        {
            poc=sr+1;
            x=sr+1;
            return x;
 
        }
        else
            kon=sr-1;
    }
}

Przerywasz wyszukiwanie binarne w miejscu, gdzie powinno być kontynuowane, trzeba przenieść return na koniec funkcji.
Co do upper_bounda i lower_bounda, to przydają się rzadko, jeżeli nie mamy vectora po którym możemy wyszukiwać binarnie to są bezużyteczne (tak się dzieje, gdy np. wyszukujemy po liczbach rzeczywistych). Dobra wiadomość jest taka, że samo wyszukiwanie binarne można napisać w trzech linijkach kodu trochę niekonwencjonalnie:

for ( int c = tab.size(); c >= 1; c /= 2)
	while ( lo + c < tab.size() && tab[lo + c] <= p )
		lo += c;

'tab' w tym przykladzie to twoje 'to', 'p' to 'x', zmienna 'c' reprezentuje coraz mniejsze skoki o ktore probujemy powiekszyc 'lo' - czyli wynik naszego wyszukiwania.