Yangiboyeva Komila Tajriba ish №5 Mavzu

Natija:

O(nlog(n)) uchun yechim:
Bunday holda, biz ulardagi elementlar orasidagi munosabatni o'rnatish uchun massivlarni saralaymiz. Va keyin, massiv elementlariga ikkita ko'rsatgich olganimizdan so'ng, biz turli massivlardagi joriy elementlardan kichikroq elementlarni emas, balki tenglikni tekshiramiz. Agar qatorda bir nechta teng elementlar mavjud bo'lsa, unda ularning soni har bir massivdagi takrorlanishlar sonining ko'paytmasiga teng bo'ladi. Ulardan birining oxiriga yetganingizdan so'ng, boshqa massivda o'tgan elementda oxirgisiga teng elementlar mavjudligini tekshirishni unutmasligingiz kerak. Faqat kichikroq elementlarni emas, balki tekshirishga arziydi. Ushbu algoritm yordamida biz o(n²) dagi mosliklarni chiziqli tekshiramiz, bu yerda n massivlar uzunligining eng kattasi, lekin buning uchun har ikkala massivni O(nlog(n) ) da saralash zarur. Shunday qilib, biz oldingi versiyaga qaraganda tezroq hisoblangan O(n log(n)) ni olamiz.
2-usul:
#include
#define N 750
using namespace std;

void merge_sort(int *arr, int n) {

if (n == 1) return;
int len_l = n / 2, len_r = n - len_l;
int l[len_l], r[len_r];
for (int i = 0; i < n; i++)
if (i < len_l) l[i] = arr[i];
else r[i - len_l] = arr[i];
merge_sort(l, len_l);
merge_sort(r, len_r);
int i = 0, j = 0;
while (i < len_l && j < len_r)
if (l[i] < r[j]) arr[i + j] = l[i++];
else arr[i + j] = r[j++];
while (i < len_l) arr[i + j] = l[i++];
while (j < len_r) arr[i + j] = r[j++];
}
int main() {
int n, m, MIN[N], MAX[N];
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int input;
cin >> input;
if (i == 0) MAX[j] = input;
else if (MAX[j] < input) MAX[j] = input;
if (j == 0) MIN[i] = input;
else if (MIN[i] > input) MIN[i] = input;
}
}
merge_sort(MAX, m);
merge_sort(MIN, n);
int i = 0, j = 0, count_i = 1, count_j = 1, counter = 0;
while (i < n && j < m) {
while (i < n-1 && MIN[i] == MIN[i+1]) {
count_i++;
i++;
}
while (j < m-1 && MAX[j] == MAX[j+1]) {
count_j++;
j++;
}
if (MIN[i] < MAX[j]) {
i++;
count_i = 1;
} else if (MIN[i] > MAX[j]) {
j++;
count_j = 1;
} else {
counter += count_i * count_j;
i++;
j++;
count_i = 1;
count_j = 1;
}
}
while (i < n && MIN[i] <= MAX[m-1]) {
while (i < n-1 && MIN[i] == MIN[i+1]) {
count_i++;
i++;
}
if (MIN[i] == MAX[m-1]) {
i++;
counter += count_i;
count_i = 1;
}
}
while (j < m && MAX[j] <= MIN[n-1]) {
while (j < m-1 && MAX[j] == MAX[j+1]) {
count_j++;
j++;
}
if (MAX[j] == MIN[n-1]) {
j++;
counter += count_j;
count_j = 1;
}
}
cout << counter;
return 0;
}
Natija:

Mustaqil ishlash uchun:
Algo: kuchli nuqtalar:
https://algo.ubtuit.uz/problem/242