# 二分搜索¶

USACO 2017 Jan S P1. Cow Dance Show 离散事件模拟 https://www.luogu.com.cn/problem/P3611
USACO 2020 Open S P1. Social Distancing 贪心 https://www.luogu.com.cn/problem/P6281
CF702C Cellular Network https://codeforces.com/contest/702/problem/C
CEOI2012 - Job Scheduling 贪心,任务规划 https://www.luogu.com.cn/problem/P6092
CF1223C Save the Nature 贪心 https://codeforces.com/problemset/problem/1223/C
Caravan Robbers, NEERC 2012, UVa1616 区间选择 https://www.luogu.com.cn/problem/UVA1616
POJ2796 Dropping tests 分数规划 http://poj.org/problem?id=2976
CF1486D Max Median 中位数判断 https://codeforces.com/problemset/problem/1486/D
Copying Books, UVa714 贪心 https://www.luogu.com.cn/problem/UVA714
BalticOI2012 - Mobile 几何思维 https://www.luogu.com.cn/problem/P7249
CF780B The Meeting Place Cannot Be Changed 区间贪心 https://codeforces.com/contest/782/problem/B
CF847B. Preparing for Merge Sort 模拟 https://codeforces.com/contest/847/problem/B
CF847E Packmen 贪心 https://codeforces.com/contest/847/problem/E
USACO 2016 Feb P P1. Load Balancing BIT, 贪心 https://www.luogu.com.cn/problem/P6172
CF1117C Magic Ship 模型转换 https://codeforces.com/problemset/problem/1117/C

## 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¶

#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;
}

#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;
}