Wykorzystaj znane rozwiązanie podobnego problemu:

wykorzystaj znane rozwiązanie podobnego problemu:

1.Słaby przywódca ciągu

Słabym przywódcą ciągu jest element, który występuje w nim więcej niż n/k razy (dla ustalonego k). Jak wykorzystać algorytm dla przywódcy (druga transformacja) do efektywnego wyznaczenia jednego ze słabych przywódców?
Ta druga transformacja

licz=0;
for(i=0; i<n; ++i){
if(licz==0){
p=tab[i];
++licz;
}else if (p==tab[i]){
++licz;
}else{
--licz;
}
}

2.Liczba inwersji (dwie posortowane tablice)

Jak efektywnie policzyć liczbę inwersji pomiędzy elementami dwóch posortowanych tablic A i B (inwersję tworzy dowolna para (i,j) taka, że A[i]>B[j])?

Wytłumaczy ktoś ja podejść do tego bo nie rozumiem

To są dwa oddzielne zadania i oba chce zrobic

Żeby wytłumaczył jak to zrobić i o co chodzi

Liczba inwersji, skoro są posortowane, to wypadałoby zrobić to w O(n). Idea jest taka: Iterujesz po pierwszej tablicy i Inkrementujesz wskaźnik drugiej do pierwszego większego elementu [od aktualnego tablicy A], jednocześnie je sumując (nie testowane za mocno):

#include <iostream>

using namespace std;

int number_inversions(int A [], int B [], int size1, int size2);
int main() {
	int A [4] = {5, 6, 10, 11};
	int B [3] = {1, 4, 10};
	cout << number_inversions(A, B, 4, 3) << endl;
	return 0;
}

int number_inversions(int A [], int B [], int size, int size2) {
	int s{0};
	int i{0};
	while (size) {
		while (*A > B[i] && i != size2) 
			i++;
		s += i;
		size--;
		A++;
	}
	return s;
}

Co do ciągu, jaki ten ciąg, skończony? Nieskończony? Jak go przyjmujemy na wejściu?

Miałam przykład taki

#include<iostream>
using namespace std;
int main(){
 int n, i, k, tab[1000], wynik;
 cin >> n;
 for (i=0; i<n; ++i){
 cin >> tab[i];
 }
 wynik = 0;
 for (i=0; i<n; ++i){
 for(k=i+1; k<n; ++k){
 if (tab[i]>tab[k]){
 ++wynik;
 }
 }
 }
 cout << wynik;
 return 0;
}

i taki "transformacja"

#include<iostream>
using namespace std;
int main(){
 int n, i, k, wynik;
 int tab[1000];
 int licz[1000];
 cin >> n;
 for (i=0; i<n; ++i){
 cin >> tab[i];
 licz[i] = 0;
 }
 k = n;
 wynik = 0;
while(k>0){
 for (i=0; i<n; ++i){
 if (tab[i]%2==1){
 ++licz[tab[i]];
 } else {
 wynik = wynik +
 licz[tab[i]+1];
 }
 }
 for (i=0; i<n; ++i){
 licz[i] = 0;
 tab[i] = tab[i]/2;
 }
 k=k/2;
}
cout << wynik;
return 0;
}

a nie wiem jak do zastosowac do tego zadania

Na to: "Jak efektywnie policzyć liczbę inwersji pomiędzy elementami dwóch posortowanych tablic A i B (inwersję tworzy dowolna para (i,j) taka, że A[i]>B[j])?" odpowiedziałem w poście powyżej. Natomiast, Twój przykład nie ma z tym nic wspólnego (liczy ile razy A[k] będzie większe od A[k+1], dla k = 0 , n). Może chodzi o sprawdzenie ilości inwersji, w danej tablicy po jej posortowaniu?
Co do drugiego, Podaj proszę, dokładny opis i interpretację danych wejściowych i wyniku (oczekiwanego).

1.Słaby przywódca ciągu

Słabym przywódcą ciągu jest element, który występuje w nim więcej niż n/k razy (dla ustalonego k). Jak wykorzystać algorytm dla przywódcy (druga transformacja) do efektywnego wyznaczenia jednego ze słabych przywódców?
Ta druga transformacja

licz = 0;
for(i=0; i<n; ++i){
 if (licz==0){
 p = tab[i];
 ++licz;
 } else if (p==tab[i]){
 ++licz;
 } else {
 --licz;
 }
}

i mam taki przykład i nic wiecej nie jest podane dlatego nie rozumiem tych zadan

#include<iostream>
using namespace std;
int lds(int x[],int n,int max){
 int i,k,best=0;
 if (x[0]>=max) return 0;
 if (n==1) return 1;
 for (i=1; i<n; ++i){
 k = lds(x+i,n-i,x[0]);
 if (best < k){
 best = k;
 }
 }
 return best+1;
}
int main(){
 int n, i, tab[1000], max;
 cin >> n;
 max = 0;
 ++n;
 for (i=1; i<n; ++i){
 cin >> tab[i];
 if (max < tab[i]){
 max = tab[i];
 }
 }
 tab[0] = max+1;
 cout << lds(tab,n,max+2)-1;
 return 0;
}

Skontaktuj się z autorem, niech Ci poda wyczerpujące info.

Dla niego to wszystko jest co powinno być

for(i=0; i<n; ++i){
 licz = 0;
 for(k=0; k<n; ++k){
 if(tab[i]==tab[k]){
 ++licz;
 }
 }
 if(2*licz>n){
 p = tab[i];
 }
}

for(i=0; i<n; ++i){
 if(unikat == tab[i]){
 ++licz;
 } else {
 if (max<licz){
 max = licz;
 p = unikat;
 }
 unikat = tab[i];
 licz = 1;
 }
}

mając to jak policzyć słabego przywódcę ?

Po pierwsze ten algorytm da poprawny wynik, przy założeniu, że ciąg zawiera przywódcę. Żeby łatwiej było zrozumieć jak masz rozbudować dla dowolnego k, najpierw inna postać szukania przywódcy ciągu:

  int tab[] = {1, 7, 1, 7, 1, 7, 2, 7, 2, 1, 2, 1, 2, 7, 7, 2};
  int licz1 = 0;
  int p1 = 0;
  for(int i = 0; i < 15; ++i){
    if (licz1 == 0) {
      p1 = tab[i];
      ++licz1;
      continue;
    }
    if (p1 == tab[i]){
      licz1++;
      continue;
    }
    licz1--;
  }
  std::cout << "wytypowany przywódca " << p1;

Poszukiwanie słabych przywódców, czyli wyrazów występujących więcej niż n/k razy wymaga utworzenia k-1 liczników, bo nie może być ich więcej. Poniżej przykład dla k = 3:

#include <iostream>

int main() {
  int tab[] = {1, 7, 1, 7, 1, 7, 2, 7, 2, 1, 2, 1, 2, 7, 7, 2};
  int licz1 = 0;
  int licz2 = 0;
  int p1 = 0;
  int p2 = 0;
  for(int i = 0; i < 15; ++i){
    if (licz1 == 0) {
      p1 = tab[i];
      ++licz1;
      continue;
    }
    if (licz2 == 0){
      p2 = tab[i];
      ++licz2;
      continue;
    }
    if (p1 == tab[i]){
      licz1++;
      continue;
    }
    if (p2 == tab[i]){
      licz2++;
      continue;
    }
    licz1--;
    licz2--;
  }
  std::cout << "wytypowani przywódcy " << (licz1 > licz2 ? p1 : p2) <<" "<<(licz1 > licz2 ? p2 : p1) ;
}

Może to Cie naprowadzi jak zbudować dla dowolnego k. Jak to nie pomoże, to tu masz przykładowe rozwiązanie, ale w C# i z użyciem słownika.