Link Sub: http://www.spoj.com/PTIT/problems/PTIT125C/
Người Gửi: Dương Lee
- Problem:
Cho dãy số N (1 <= N <= 1,000,000, N lẻ) phần tử đánh số từ 1 đến N, ban đầu có giá trị là 0. Có tất cả K (1<=K<=25,000) truy vấn, mỗi truy vấn có dạng "A B" sẽ thực hiện tăng các phần tử trong đoạn [A,B] lên một đơn vị.
Sau khi thực hiện K truy vấn, tìm giá trị phần tử trung vị (phần tử ở chính giữa nếu sắp xếp dãy tăng dần) của dãy.
InputSau khi thực hiện K truy vấn, tìm giá trị phần tử trung vị (phần tử ở chính giữa nếu sắp xếp dãy tăng dần) của dãy.
- Dòng 1: N và K
- Dòng 2..K+1: Mỗi dòng chứa 1 truy vấn có dạng "A B" (1<=A,B<=N) có ý nghĩa như trong đề bài.
- Dòng 2..K+1: Mỗi dòng chứa 1 truy vấn có dạng "A B" (1<=A,B<=N) có ý nghĩa như trong đề bài.
Output
Example:
Giá trị phần tử trung vị của dãy sau khi hiện K truy vấn.
Input
7 4
5 5
2 4
4 6
3 5
Output:
1
- Solution:
Giải thích: Sau khi thực hiện các truy vấn dãy trở thành 0,1,2,3,3,1,0. Sắp xếp lại thành 0,0,1,1,2,3,3.
- Tư tưởng:
Các bạn thấy mỗi truy vấn ta tạo ra một list các giá trị giống nhau.
VD:
5 5 -> 0000100
2 4 -> 0111100
4 6 -> 0112210
3 5 -> 0123310
Nhưng vấn đề là "Nếu duyệt tuyến tính cho từng truy vấn chắc chắn sẽ quá time" (0.1s -> phức tạp max = O(n)).
Vậy ta có thể nghĩ đến cách chỉ lấy đại diện các số thôi thay vì thay đổi cả khoảng.
VD như chuyển về dạng đóng mở ngoặc chẳng hạn "(" ")";
VD:
Như ta thấy ảnh trên mỗi lần qua mở ngoăc "(" thì số trong khoảng đó sẽ tăng lên 1 nấc, qua đóng ngoặc ")" thì số trong khoảng giảm đi 1 nấc.
Từ đó ta có thể liệt kê tất cả danh sách các số sau k truy vấn. Sau đó chỉ việc sắp xếp và in ra phần tử trung vị.
(sort sử dụng dưới đây là heapsort)
- Tư tưởng:
Các bạn thấy mỗi truy vấn ta tạo ra một list các giá trị giống nhau.
VD:
5 5 -> 0000100
2 4 -> 0111100
4 6 -> 0112210
3 5 -> 0123310
Nhưng vấn đề là "Nếu duyệt tuyến tính cho từng truy vấn chắc chắn sẽ quá time" (0.1s -> phức tạp max = O(n)).
Vậy ta có thể nghĩ đến cách chỉ lấy đại diện các số thôi thay vì thay đổi cả khoảng.
VD như chuyển về dạng đóng mở ngoặc chẳng hạn "(" ")";
VD:
Từ đó ta có thể liệt kê tất cả danh sách các số sau k truy vấn. Sau đó chỉ việc sắp xếp và in ra phần tử trung vị.
(sort sử dụng dưới đây là heapsort)
- Code:
C++:
https://ideone.com/DFQsfh
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct data
{
int close;
int open;
data (int c, int p)
{
close = c;
open = p;
}
data ()
{
close = 0;
open = 0;
}
} data;
data arr[1000006];
int main ()
{
int n, k;
cin>>n>>k;
int A, B;
for (int i=0; i<k; i++)
{
cin>>A>>B;
arr[A].open++;
arr[B].close++;
}
vector <int> list;
int so = 0;
for (int i=1; i<=n; i++)
{
so += arr[i].open;
list.push_back(so);
so -= arr[i].close;
}
sort(list.begin(), list.end());
cout<<list[(n/2)];
return 0;
}JAVA:
...Python:
...