跳转至

二分搜索

题目 类型 链接
派(Pie, NWERC2006, POJ3311) https://open.kattis.com/problems/pie
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

这道题需要注意精度,因为\(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;
}