二分搜索¶
Pie¶
#include <bits/stdc++.h>
using namespace std;
const int N = 10000 + 10;
const double PI = acos(-1.0);
const double eps = 1e-5;
int n, f;
double v[N];
bool check(double x) {
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += floor(v[i] / x);
}
return ans >= f + 1;
}
int main() {
int tc;
cin >> tc;
while (tc--) {
cin >> n >> f;
double maxa = -1;
for (int i = 0; i < n; ++i) {
int r;
cin >> r;
v[i] = PI * r * r;
maxa = max(maxa, v[i]);
}
double l = 0, r = PI * 10001 * 10001;
while (r - l > eps) {
double mid = (l + r) / 2;
if (check(mid)) {
l = mid;
} else {
r = mid;
}
}
printf("%f\n", l);
}
}Cow Dance Show¶
#include <bits/stdc++.h>
using namespace std;
const int N = 10000 + 7;
int n, t, d[N];
bool check(int k) {
int y = 0; // 上一头牛的结束时间
int ans = 0; // 时间的和
priority_queue<int, vector<int>, greater<int>> q; // 保存结束时间
for (int i = 0; i < k; ++i) {
q.push(d[i]); //注意：只有这里是时间(不是结束时间)
}
for (int i = k; i < n; ++i) {
ans += q.top() - y; // 这头牛的结束时间 - 上头牛的结束时间 = 多用的时间
y = q.top(); // 这头牛的结束时间
q.pop();
q.push(d[i] + y);
if (ans > t) return false; // 超过时间
q.push(t);
}
while (q.size()) { // 检查最后的几位
ans += q.top() - y;
y = q.top();
q.pop();
if (ans > t) return false;
}
return true;
}
int main() {
cin >> n >> t;
for (int i = 0; i < n; ++i) cin >> d[i];
int l = 0, r = N;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid))
r = mid - 1;
else
l = mid + 1;
}
cout << l << endl;
}Social Distancing¶
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define INF 2000000000
#define FF first
#define SS second
int n, m;
vector<pair<LL, LL>> intervals;
bool ok(LL d) {
LL prev = -1LL * INF * INF;
int cnt = 0;
for (auto& i : intervals) {
while (max(prev + d, i.FF) <= i.SS) {
prev = max(prev + d, i.FF);
cnt++;
if (cnt >= n) break;
}
if (cnt >= n) break;
}
return (cnt >= n);
}
int main() {
cin >> n >> m;
intervals.resize(m);
for (int i = 0; i < m; ++i) cin >> intervals[i].FF >> intervals[i].SS;
sort(intervals.begin(), intervals.end());
LL lo = 1;
LL hi = 1LL * INF * INF;
LL res = -1;
while (lo <= hi) {
LL mid = (lo + hi) / 2;
if (ok(mid)) {
res = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
cout << res << "\n";
}Cellular Network¶
这道题需要注意精度，因为\(10^{-9} \le b_i \le 10^9\)，所以\(r\)最大会达到\(2\times 10^9\)，int装不下
题解给了一种\(O(n)\)的双指针做法
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
ll a[N], b[N];
int n, m;
ll L[N], R[N];
bool check(ll r) {
for (int i = 0; i < m; ++i) {
L[i] = b[i] - r;
R[i] = b[i] + r;
}
int j = 0;
for (int i = 0; i < n; ++i) {
ll cur = a[i];
bool ok = false;
while (L[j] <= cur) {
if (R[j] >= cur) {
ok = true;
break;
} else {
j++;
if (j > m) {
return false;
}
}
}
if (!ok) {
return false;
}
}
return true;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < m; ++i) cin >> b[i];
ll lo = 0, hi = 2e9 + 7;
long long res = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
// cout << mid << ' ';
if (check(mid)) {
res = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
cout << res << endl;
}Job Scheduling¶
/**
* 时间复杂度：？？？
**/
#include <bits/stdc++.h>
using namespace std;
const int maxm = 1e6 + 7;
int N, D, M;
int job[maxm];
vector<int> day[maxm];
// 另外，num是多余的
struct node {
int num, time;
};
bool check(int x) {
if (!x) return false; // 特判一下x=0的情况，否则，二分的左边界不能为0
// 具体原因是，x=0可以完美地绕过下边的测试而抵达return true
queue<node> q; // 用于推迟某天内完不成的任务
for (int i = 1; i <= N; ++i) { // 这道N只有100，非常小
int mach = x; // 今天的机器数；每天一开始都是x
while (q.size()) {
auto [num, time] = q.front();
q.pop();
if (time + D < i) { // 超过时间限制
return false;
}
--mach;
if (!mach) break; // 机器数为0
}
if (q.size()) {
auto [num, time] = q.front();
if (time + D < i) return false;
}
for (auto v : day[i]) {
if (mach)
--mach;
else {
q.push({v, i});
}
}
}
return true;
}
int main() {
cin >> N >> D >> M;
for (int i = 1; i <= M; ++i) {
cin >> job[i];
day[job[i]].push_back(i);
}
int lo = 0, hi = M, res = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
// cout << mid << endl;
if (check(mid)) {
res = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
cout << res << endl;
}
Save the Nature¶
/* WA */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
typedef long long ll;
ll n, x, a, y, b, k;
int p[N];
bool check(int len) {
ll ans = 0;
ll cX, cY, cXY;
ll t = a / __gcd(a, b) * b;
cXY = len / t;
cX = len / a - cXY;
cY = len / b - cXY;
for (int i = 0; i < cXY; ++i) {
ans += p[i] * (x + y);
}
for (int i = cXY; i < cXY + cX; ++i) {
ans += p[i] * x;
}
for (int i = cXY + cX; i < cXY + cX + cY; ++i) {
ans += p[i] * y;
}
return ans >= k;
}
int main() {
// freopen("in.txt", "r", stdin);
int q;
cin >> q;
while (q--) {
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> p[i];
p[i] /= 100;
}
cin >> x >> a >> y >> b >> k;
sort(p, p + n, greater<int>());
if (x < y) {
swap(x, y);
swap(a, b);
}
int lo = 0, hi = n + 1, ans;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (check(mid)) {
hi = mid - 1;
} else {
ans = mid;
lo = mid + 1;
}
}
if (lo > n) lo = -1;
cout << lo << endl;
}
}Caravan Robbers¶
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxn = 1e5+5;
const long double eps = 1e-11;
struct line {
int l, r;
bool operator < (const line &x) const {
return l < x.l || (l == x.l && r < x.r);
}
} L[maxn];
int n;
bool judge(long double x) {
long double cur = 0;
for (int i = 0; i < n; i++) {
cur = max(cur, (long double)L[i].l);
cur += x;
if (cur - L[i].r > eps) return false;
}
return true;
}
int main() {
while(scanf("%d", &n) == 1 && n) {
for (int i = 0; i < n; i++)
scanf("%d%d", &L[i].l, &L[i].r);
sort(L, L + n);
long double l = 0, r = L[n - 1].r;
while (r - l > eps) {
long double mid = (l + r) / 2;
if (judge(mid)) l = mid;
else r = mid;
}
int p, q;
for (q = 1; q <= n + 1; q++) {
p = round(l * q);
long double t = (long double)p / q;
if (fabs(t - l) < eps) {
break;
}
}
printf("%d/%d\n", p, q);
}
return 0;
}Dropping Tests¶
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;
int n, k;
struct node {
int a, b;
double p;
} x[1009];
bool cmp(node a, node b) { return a.p > b.p; }
bool check(double xx) {
for (int i = 1; i <= n; i++) x[i].p = 1.0 * x[i].a - 1.0 * x[i].b * xx;
sort(x + 1, x + 1 + n, cmp);
double sum1 = 0, sum2 = 0;
for (int i = 1; i <= n - k; i++) sum1 += x[i].a, sum2 += x[i].b;
return sum1 / sum2 > xx;
}
int main() {
while (~scanf("%d%d", &n, &k)) {
if (!n && !k) break;
for (int i = 1; i <= n; i++) scanf("%d", &x[i].a);
for (int i = 1; i <= n; i++) scanf("%d", &x[i].b);
double l = 0, r = 1;
while (fabs(r - l) > 1e-8) {
double mid = (l + r) / 2;
if (check(mid))
l = mid;
else
r = mid;
}
printf("%.0f\n", l * 100);
}
return 0;
}Max median¶
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
const int INF = 2e8+7;
int n, k;
int a[maxn], b[maxn];
bool check(int x) {
for(int i=0; i<n; ++i) {
if(a[i]>=x) b[i]=1;
else if(a[i]<x) b[i]=-1;
}
for(int i=1; i<n; ++i) b[i]+=b[i-1];
int mn=0, mx = b[k-1];
for(int i=k; i<n; ++i) {
mn = min(mn, b[i-k]);
mx = max(mx, b[i]-mn);
}
return mx > 0;
}
int solve() {
int l=0, r=maxn;
int mid;
while(l+1<r) {
mid = (l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
cout<<l<<'\n';
return 0;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>k; for(int i=0; i<n; ++i) cin>>a[i];
solve();
return 0;
}
Copying books¶
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k, T, a[505], p[505];
bool check(int w) {
int tot = 0, t = 0;
for (int i = 1; i <= n; i = ++i) {
tot += a[i];
if (tot > w) tot = a[i], t++;
}
return t < k;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> T;
while (T--) {
memset(p, 0, sizeof(p));
int l = 0, r = 0, val = 0;
cin >> n >> k;
for (int i = 1; i <= n; i = ++i) cin >> a[i], l = max(l, a[i]), r += a[i];
while (l < r) {
int mid = l + r >> 1;
if (check(mid))
r = mid; //二分
else
l = mid + 1;
}
k--;
for (int i = n; i >= 1;
i--) { // 因为要求前面的分组之和尽可能小，所以倒序遍历
val += a[i];
if (val > l)
val = a[i], p[i] = 1,
k--; //当前缀和大于答案时前缀和清零，再加上当前的数
}
for (int i = 1; i <= n && k; i = ++i)
if (!p[i]) //如果当前已经要输出斜杠，就不统计了
p[i] = 1, k--;
for (int i = 1; i < n; i = ++i) {
cout << a[i] << ' ';
if (p[i]) cout << '/' << ' ';
}
cout << a[n] << '\n';
}
return 0;
}Mobile¶
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,L;
int X[1000005],Y[1000005];
bool check(double r)
{
double x=0,From,To;
for(int i=1;i<=n;i++)
{
From=-sqrt(1.0*r*r-1.0*Y[i]*Y[i])+X[i];
To=sqrt(1.0*r*r-1.0*Y[i]*Y[i])+X[i];
if(From<=x&&x<=To) x=To;
}
return x>=L;
}
int main() {
scanf("%d %d",&n,&L);
for(int i=1;i<=n;i++) scanf("%d %d",&X[i],&Y[i]);
double l=0,r=1e9,mid,Ans;
while(r-l>0.0005)
{
mid=(l+r)/2;
if(check(mid)) r=mid,Ans=mid;
else l=mid;
}
printf("%.6f",Ans);
return 0;
}CF780B The Meeting Place Cannot Be Changed¶
#include <bits/stdc++.h>
using namespace std;
const int N = 60000 + 7;
const double eps = 1e-9;
int n;
int x[N], v[N];
bool check(double t) {
double l = -2e9, r = 2e9;
for (int i = 0; i < n; ++i) {
l = max(l, x[i] - t * v[i]);
r = min(r, x[i] + t * v[i]);
}
return l <= r;
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i) cin >> x[i];
for (int i = 0; i < n; ++i) cin >> v[i];
double lo = 0, hi = 1e9 + 7;
for (int i = 0; i < 1000; ++i) {
// while (hi - lo > eps) { // TLE
double mid = (lo + hi) / 2;
if (check(mid)) {
hi = mid;
} else {
lo = mid;
}
}
printf("%.9f", (hi + lo) / 2);
}
/*
TLE hack:
3
1 1000000000 2
1 2 1000000000
*/Preparing for Merge Sort¶
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200000 + 7;
int a[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
vector<int> v[n + 1];
for (int i = 0; i <= n; ++i) {
v[i].push_back(-(int)1e9 - 7);
}
for (int i = 0; i < n; ++i) {
int l = 0, r = n;
while (r - l > 1) {
int m = (l + r) / 2;
if (v[m].back() <= a[i]) {
r = m;
} else {
l = m;
}
}
v[r].push_back(a[i]);
}
for (int i = 0; i <= n; ++i) {
if (v[i].size() > 1) {
for (int j = 1; j < (int)v[i].size(); ++j) {
cout << v[i][j] << ' ';
}
cout << '\n';
}
}
}Pacmen¶
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int n;
char s[N];
vector<int> pacman, food;
int main() {
cin >> n >> s;
for (int i = 0; i < n; ++i) {
if (s[i] == 'P') pacman.push_back(i);
if (s[i] == '*') food.push_back(i);
}
int lo = 0, hi = 3 * n;
while (lo < hi) {
int mid = (lo + hi) / 2;
int ptr = 0;
for (int x : pacman) {
int from = x, to = x;
while (ptr < (int)food.size()) {
from = min(from, food[ptr]);
to = max(to, food[ptr]);
int need = to - from + min(to - x, x - from);
if (need > mid) break;
ptr++;
}
}
if (ptr == (int)food.size()) {
hi = mid;
} else {
lo = mid + 1;
}
}
cout << lo;
}Load Balancing P¶
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
struct cow {
int x, y;
bool operator<(const cow& a) const { return y < a.y; }
} c[N];
int n, sb[N], xb[N];
#define lowbit(x) (x & -x)
void change(int a[], int x, int k) {
while (x <= n) {
a[x] += k, x += lowbit(x);
}
}
int query(int a[], int x) {
int res = 0;
while (x > 0) {
res += a[x], x -= lowbit(x);
}
return res;
}
bool check(int x) {
memset(sb, 0, sizeof(sb));
memset(xb, 0, sizeof(xb));
for (int i = 1; i <= n; ++i) change(sb, c[i].x, 1);
int st = n, xt = 0, zs = 1, zx = n;
for (int t, i = 1, j = 1; i <= n; i = j) {
while (c[i].y == c[j].y) {
change(sb, c[j].x, -1);
change(xb, c[j].x, 1);
st--, xt++, j++;
}
while (zs <= n && query(sb, zs) <= x) {
zs++;
}
zs--;
while (zs > 0 && query(xb, zx) > x) {
zx--;
}
t = min(zx, zs);
if (xt - query(xb, t) <= x && st - query(sb, t) <= x) {
return true;
}
}
return false;
}
pair<int, int> p[N];
int tot, mid, l, r, ans;
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> c[i].x >> c[i].y;
p[i].first = c[i].x, p[i].second = i;
}
sort(p + 1, p + n + 1);
for (int i = 1; i <= n; ++i) {
if (p[i].first != p[i - 1].first) {
tot++;
}
c[p[i].second].x = tot;
}
sort(c + 1, c + n + 1);
l = 1, r = n;
while (l <= r) {
mid = (l + r) / 2;
if (check(mid)) {
r = mid - 1;
ans = mid;
} else {
l = mid + 1;
}
}
cout << ans << endl;
return 0;
}Magic Ship¶
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 100009;
pair<int, int> st, fi;
int n;
string s;
string mv = "UDLR";
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
pair<int, int> d[N];
int main() {
cin >> st.x >> st.y >> fi.x >> fi.y;
cin >> n >> s;
for (int i = 0; i < n; ++i) {
int id = -1;
for (int j = 0; j < 4; ++j)
if (mv[j] == s[i]) id = j;
assert(id != -1);
d[i + 1] = make_pair(d[i].x + dx[id], d[i].y + dy[id]);
}
long long l = 0, r = 1e18;
while (r - l > 1) {
long long mid = (l + r) / 2;
long long cnt = mid / n, rem = mid % n;
long long x = st.x + d[rem].x + cnt * 1LL * d[n].x;
long long y = st.y + d[rem].y + cnt * 1LL * d[n].y;
long long dist = abs(x - fi.x) + abs(y - fi.y);
if (dist <= mid)
r = mid;
else
l = mid;
}
if (r > 5e17) r = -1;
cout << r << endl;
return 0;
}