Bài toán số trung vị

c++

(Đạt Phạm) #1

Cho N dãy số không giảm A1, A2, …, AN, mỗi dãy gồm L số nguyên (dãy số được gọi là không giảm nếu mỗi phần tử đứng sau là lớn hơn hoặc bằng phần tử đứng trước). Xét hai dãy Ai và Aj (1≤ i, j ≤ N), ta gọi dãy gộp (ký hiệu là Aij) của hai dãy Ai, Aj là dãy gồm tất cả 2L phần tử của hai dãy Ai, Aj được sắp xếp theo thứ tự không giảm và phần tử đứng ở vị trí thứ L trong dãy gộp được gọi là phần tử trung vị của nó.

Ví dụ: Xét hai dãy số

Ai = (1 3 4 5 6); Aj = (0 1 5 6 7).

Khi đó dãy gộp Aij từ hai dãy đã cho là

0 1 1 3 4 5 5 6 6 7

có phần tử trung vị là 4.
Yêu cầu: Tính tổng của tất cả các phần tử trung vị của tất cả các dãy gộp Aij với 1≤ i < j ≤ N.

#include <bits/stdc++.h>
using namespace std;
ifstream fi ("TV.INP");
ofstream fo ("TV.OUT");

int main()
{
    int n,l;
    fi >> n >> l;

    long long arr [n+1][l+1];

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=l; j++)
        {
            fi >> arr[i][j];
        }
    }

    long long sum = 0;

    for(int i=1; i<n; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            int ai,aj;
            ai = aj = 0;
            while(true)
            {
                int temp;
                if(arr[i][ai+1] < arr[j][aj+1])
                {
                    ai ++;
                    temp = arr[i][ai];
                }
                else
                {
                    aj ++;
                    temp = arr[j][aj];
                }
                if(ai + aj == l)
                {
                    sum += temp;
                    break;
                }
            }
        }
    }

    fo << sum;

    return 0;
}

Đây là code của mình. Nhưng mà nó không chạy được hết ràng buộc: n<=200 và 1<=L<=20000
Run code + Demo Test: https://ideone.com/qEZ6Gc
Test với n = 200 và L=20000: https://secufiles.com/r9A3/Test.txt
Cho mình hỏi là phải tối ưu hóa thế nào để đáp ứng yêu cầu ?


(Shiharoku) #2

Của mình thì có gọn hơn một chút nhưng mà vẫn lâu quá. (O(n2l) lận :laughing:)

Code
#include <iostream>

int median(int *ai, int *aj, int k) {
	int i = 0, j = 0;
	int coutn = 1;
	while (coutn < k) {
		ai[i] <= aj[j] ? i++ : j++;
		coutn++;
	}
	return ai[i] < aj[j] ? ai[i] : aj[j];
}


int main() {
	int n,l;
	std::cin >> n >> l;
	int arr[n][l] = {{0}};
	int sum = 0;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < l; j++)
			std::cin >> arr[i][j];

	for (int i = 0; i < n - 1; i++)
		for (int j = i + 1; j < n; j++)
			sum += median(arr[i], arr[j], l);

	std::cout << "\nSum is: " << sum;
	return 0;
}
Test

https://ideone.com/qSIlbR


(Đạt Phạm) #3

Dùng mảng 2 chiều riêng cái khoản nhập dl vào cũng đã xịt rồi :sweat_smile:


(Shiharoku) #4

Vậy thì do đề thôi. :laughing:

Mà mấy cái kiểu này mình tưởng là nó sẽ nhập sẵn cho mình, còn mình chỉ việc submit solution thôi chứ. Kiểu như bên https://leetcode.com/ á. :slight_smile:


(Đạt Phạm) #5

Mình hỏi nên demo vậy thôi :sunglasses:


(Shiharoku) #6

:sweat_smile:


83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?