fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6. typedef long double ld;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10. const ld eps = 1e-3; 
  11. const int N = 1e5 + 5; 
  12.  
  13. int n; 
  14. int a[N]; 
  15.  
  16. // Giả sử ta cần check giá trị trung bình cộng là avg (average)
  17. // Xét một cách chọn bất kì thoả mãn yêu cầu {i1, i2, ..., in} 
  18. // Ta có: (a[i1] + a[i2] + ... + a[in]) / n >= avg
  19. //    <=>  a[i1] + a[i2] + ... + a[in] >= n * avg 
  20. //    <=>  a[i1] + a[i2] + ... + a[in] - n * avg >= 0 
  21. //    <=> (a[i1] - avg) + (a[i2] - avg) + ... + (a[in] - avg) >= 0
  22. // Từ đây ta có thể đặt mảng b với b[i] = (a[i] - avg), việc còn lại là check max_sum(b) >= 0
  23. // Với giá trị avg càng lớn thì giá trị b[i] càng nhỏ
  24. //     giá trị avg càng nhỏ thì giá trị b[i] càng lớn 
  25. // => Tìm kiếm nhị phân đáp án
  26.  
  27. ld f[N]; // f[i] = Tổng lớn nhất thoả mãn điều kiện tính đến vị trí thứ i 
  28.  
  29. bool checkAvg(ld avg) {
  30. 	f[0] = 0;  
  31. 	f[1] = a[1] - avg;
  32.  
  33. 	for (int i = 2; i <= n; i++) {
  34. 		ld x = a[i] - avg; 
  35. 		f[i] = x + max(f[i - 1], f[i - 2]); 
  36. 	} 
  37.  
  38. 	return (max(f[n], f[n - 1]) + eps >= 0); 
  39. }
  40.  
  41. ld maxAvg() {
  42. 	ld l = 1, r = 1e9, ans = -1;  
  43.  
  44. 	while (l - eps <= r) {
  45. 		ld mid = (l + r) / 2; 
  46.  
  47. 		if (checkAvg(mid)) {
  48. 			ans = mid;  
  49. 			l = mid + eps; 
  50. 		}
  51. 		else {
  52. 			r = mid - eps; 
  53. 		}
  54. 	}
  55.  
  56. 	return ans; 
  57. }
  58.  
  59. // Với med thì các em có thể xem lại ý tưởng ở bài D. Max Median (Codeforces)
  60.  
  61. int dp[N]; // dp[i] = Tổng lớn nhất thoả mãn điều kiện tính đến vị trí thứ i 
  62.  
  63. bool checkMed(int med) {
  64. 	dp[0] = 0;  
  65. 	dp[1] = (a[1] >= med) ? 1 : -1;  
  66.  
  67. 	for (int i = 2; i <= n; i++) {
  68. 		int x = (a[i] >= med) ? 1 : -1; 
  69. 		dp[i] = x + max(dp[i - 1], dp[i - 2]);  
  70. 	}
  71.  
  72. 	return (max(dp[n], dp[n - 1]) > 0); 
  73. }
  74.  
  75. int maxMedian() {
  76. 	int l = 1, r = 1e9, ans = -1; 
  77.  
  78. 	while (l <= r) {
  79. 		int mid = (l + r) >> 1; 
  80.  
  81. 		if (checkMed(mid)) {
  82. 			ans = mid;  
  83. 			l = mid + 1; 
  84. 		}
  85. 		else {
  86. 			r = mid - 1; 
  87. 		}
  88. 	}
  89.  
  90. 	return ans; 
  91. }
  92.  
  93. int main() {
  94. 	ios::sync_with_stdio(0); cin.tie(0);  	
  95. 	cin >> n; 
  96. 	for (int i = 1; i <= n; i++) cin >> a[i];
  97.  
  98. 	cout << fixed << setprecision(17) << maxAvg() << '\n'; 
  99. 	cout << maxMedian() << '\n'; 
  100. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
7
3 1 4 1 5 9 2
stdout
copy 
5.24997823184419030
4
https://ideone.com/hvLwU6
language:
C++14 (gcc 8.3)
created:
1 year 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!