fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. // - Bài toán 1: Cho dãy a gồm n phần tử, mỗi thao tác được tăng/giảm một phần tử bất kì (x = x - 1 hoặc x = x + 1) 
  12. //   Tính số thao tác ít nhất để tất cả n phần tử bằng nhau?
  13. // - Hay nói cách khác, cần tìm x để cực tiểu hoá tổng |a(i) - x|
  14. // => Đáp án: x là trung vị (median) của a 
  15.  
  16. // - Áp dụng vào bài này, nhiệm vụ của ta là với mỗi đoạn k phần tử, cần tìm được phần tử trung vị (median),
  17. //   tổng và số lượng phần tử <= med, tổng và số lượng phần tử > med
  18. // - Ở đây có nhiều cách xử lí offline (Fenwick Tree,...), nhưng có cách làm online kinh điển:
  19. // - Để ý rằng median chính là phần tử nằm ở chính giữa mảng sau khi sort nên ở đây ta có thể duy trì 2 multiset lo, hi 
  20. // - multiset lo sẽ là tập các phần tử nằm ở nửa trái (<= med), cùng với sum_lo để lưu tổng
  21. //   multiset hi sẽ là tập các phần tử nằm ở nửa phải (> med), cùng với sum_hi để lưu tổng
  22. // - Ta sẽ luôn giữ cho 2 multiset lo, hi được cân bằng:
  23. //   lo.size() >= hi.size() và |lo.size() - hi.size()| <= 1
  24. //   Suy ra hi.size() <= lo.size() <= hi.size() + 1
  25. // - Khi đó, phần tử trung vị chính là *lo.rbegin() 
  26. // - Mỗi khi thêm, xoá phần tử thì ta sẽ gọi hàm rebalance() để tái cân bằng theo điều kiện trên
  27.  
  28. const int N = 2e5 + 5; 
  29.  
  30. int n, k;  
  31. int a[N]; 
  32.  
  33. multiset<int> lo, hi;  
  34. ll sum_lo = 0, sum_hi = 0;  
  35.  
  36. void rebalance() {
  37. 	while (lo.size() < hi.size()) {
  38. 		int x = *hi.begin(); hi.erase(hi.find(x)); 
  39. 		sum_hi -= x;  
  40. 		lo.insert(x); 
  41. 		sum_lo += x;
  42. 	}
  43. 	while (lo.size() > hi.size() + 1) {
  44. 		int x = *prev(lo.end()); lo.erase(lo.find(x));  
  45. 		sum_lo -= x;  
  46. 		hi.insert(x); 
  47. 		sum_hi += x; 
  48. 	}
  49. }
  50.  
  51. void add(int x) {
  52. 	if (lo.empty() || x <= *lo.rbegin()) {
  53. 		lo.insert(x); 
  54. 		sum_lo += x; 
  55. 	}
  56. 	else {
  57. 		hi.insert(x); 
  58. 		sum_hi += x; 
  59. 	}
  60. 	rebalance(); 
  61. }
  62.  
  63. void remove(int x) {
  64. 	if (lo.find(x) != lo.end()) {
  65. 		lo.erase(lo.find(x));  
  66. 		sum_lo -= x;  
  67. 	}
  68. 	else {
  69. 		hi.erase(hi.find(x)); 
  70. 		sum_hi -= x; 
  71. 	}
  72. 	rebalance();  
  73. }
  74.  
  75. ll getCost() {
  76. 	ll med = *lo.rbegin();   
  77. 	ll cost = (med * (ll)lo.size() - sum_lo) + (sum_hi - med * (ll)hi.size()); 
  78. 	return cost; 
  79. }
  80.  
  81. int main() {
  82. 	ios::sync_with_stdio(false); 
  83. 	cin.tie(nullptr); 	
  84. 	cin >> n >> k; 
  85. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  86.  
  87. 	for (int i = 1; i <= k; i++) add(a[i]);  
  88. 	cout << getCost() << ' '; 
  89.  
  90. 	for (int i = k + 1; i <= n; i++) {
  91. 		add(a[i]);  
  92. 		remove(a[i - k]);  
  93. 		cout << getCost() << ' '; 
  94. 	}
  95. }
  96.  
  97.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
8 3
2 4 3 5 8 1 2 1
stdout
copy 
2 2 5 7 7 1
https://ideone.com/l6j0Tb
language:
C++14 (gcc 8.3)
created:
159 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!