Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- constexpr int N = 1e3 + 5;
- int n, k;
- int a[N * 2];
- void Read()
- {
- cin >> n;
- for (int i = 1; i <= n; ++i)
- cin >> a[i];
- cin >> k;
- }
- bool Check(int R)
- {
- for (int i = 1; i <= n; ++i)
- {
- int cntIntervals = 1;
- int minInInterval = i;
- for (int j = i + 1; j < i + n; ++j)
- if (a[j] - a[minInInterval] > R * 2)
- {
- ++cntIntervals;
- minInInterval = j;
- }
- // cntIntervals chính là số đoạn cần để phủ a[i…i+n-1]
- if (cntIntervals <= k) // Chỉ tạo ra không quá k đoạn => Không dùng nhiều hơn k trạm phát sóng
- return true;
- }
- return false;
- }
- void Solve()
- {
- sort(a + 1, a + n + 1);
- for (int i = 1; i <= n; ++i)
- a[i + n] = a[i] + 1000000;
- int l = 0, m, h = 1e6;
- while (l <= h)
- {
- m = (l + h) / 2;
- if (Check(m))
- h = m - 1;
- else
- l = m + 1;
- }
- cout << l;
- }
- int32_t main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- Read();
- Solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement