6 二分参考代码

RonChen / 2023-08-06 / 原文

P2249 [深基13.例1] 查找

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 1000005;
int a[MAXN];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    while (m--) {
        int q; scanf("%d", &q);
        int idx = lower_bound(a + 1, a + n + 1, q) - a;
        printf("%d ", idx == n || a[idx] != q ? -1 : idx);
    }
    return 0;
}

P1102 A-B 数对

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 200005;
int a[MAXN];
int main()
{
    int n, c;
    scanf("%d%d", &n, &c);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    LL ans = 0;
    for (int i = 1; i <= n; i++) 
        ans += upper_bound(a + 1, a + n + 1, a[i] + c) - lower_bound(a + 1, a + n + 1, a[i] + c);
    printf("%lld\n", ans);
    return 0;
}

P1678 烦恼的高考志愿

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
const int INF = 1e9;
int a[MAXN];
int main()
{
    int m, n;
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; ++i) scanf("%d", &a[i]);
    sort(a, a + m);
    LL ans = 0;
    while (n--) {
        int x;
        scanf("%d", &x);
        int idx = lower_bound(a, a + m, x) - a;
        int cur = INF;
        if (idx < m) cur = min(cur, abs(a[idx] - x));
        if (idx > 0) --idx;
        cur = min(cur, abs(a[idx] - x));
        ans += cur;
    }
    printf("%lld\n", ans);
    return 0;
}

P1824 进击的奶牛

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5;
int x[MAXN], n, c;
bool check(int mid) {
    int res = 1, pre = x[0];
    for (int i = 1; i < n; i++) {
        if (x[i] - pre >= mid) {
            res++;
            pre = x[i];
        }
    }
    return res >= c;
}
int main()
{
    scanf("%d%d", &n, &c);
    for (int i = 0; i < n; i++) scanf("%d", &x[i]);
    sort(x, x + n);
    int l = 0, r = x[n - 1] - x[0], ans;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid; l = mid + 1;
        } else r = mid - 1;
    }
    printf("%d\n", ans);
    return 0;
}

P1873 [COCI2011-2012#5] EKO / 砍树

#include <cstdio>
using namespace std;
typedef long long LL;
const int MAXN = 1000005;
int n, m;
int h[MAXN];
bool check(int x) {
    LL sum = 0;
    for (int i = 0; i < n; ++i) {
        if (h[i] > x) sum += h[i] - x;
        if (sum >= m) return true;
    }
    return false;
}
int main()
{
    scanf("%d%d", &n, &m);
    int l = 0, r = 0, ans;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &h[i]);
        if (h[i] > r) r = h[i];
    }
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            l = mid + 1; ans = mid;
        } else r = mid - 1;
    }
    printf("%d\n", ans);
    return 0;
}

P2440 木材加工

#include <cstdio>
typedef long long LL;
const int MAXN = 100005;
int n, k, l[MAXN];
bool check(int x) {
    LL sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += l[i] / x;
        if (sum >= k) return true;
    }
    return false;
}
int main()
{
    scanf("%d%d", &n, &k);
    LL sum = 0;
    int L = 1, R = 0, ans;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &l[i]);
        sum += l[i];
        if (l[i] > R) R = l[i];
    }
    if (sum < k) {
        printf("0\n");
        return 0;
    }
    while (L <= R) {
        int mid = (L + R) / 2;
        if (check(mid)) {
            L = mid + 1; ans = mid;
        } else R = mid - 1;
    }
    printf("%d\n", ans);
    return 0;
}

P2678 [NOIP2015 提高组] 跳石头

#include <cstdio>
typedef long long LL;
const int MAXN = 50005;
int l, n, m, d[MAXN];
bool check(int x) {
    int cnt = 0, pre = 0;
    for (int i = 0; i < n; ++i) {
        if (d[i] - pre < x) ++cnt;
        else pre = d[i];
    }
    if (l - pre < x && pre != 0) ++cnt;
    return cnt <= m;
}
int main()
{
    scanf("%d%d%d", &l, &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", &d[i]);
    if (m == n) {
        printf("%d\n", l);
        return 0;
    }
    int L = 1, R = l, ans;
    while (L <= R) {
        int mid = (L + R) / 2;
        if (check(mid)) {
            L = mid + 1; ans = mid;
        } else R = mid - 1;
    }
    printf("%d\n", ans);
    return 0;
}

P1182 数列分段 Section II

#include <cstdio>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
int n, m, a[MAXN];
bool check(LL x) {
    LL sum = 0;
    int g = 1;
    for (int i = 0; i < n; ++i) {
        if (sum + a[i] <= x) {
            sum += a[i];
        } else {
            ++g;
            sum = a[i];
        }
    }
    return g > m;
}
int main()
{
    scanf("%d%d", &n, &m);
    LL L = 0, R = 0, ans;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        if (a[i] > L) L = a[i];
        R += a[i]; 
    }
    while (L <= R) {
        LL mid = (L + R) / 2;
        if (check(mid)) L = mid + 1;
        else {
            R = mid - 1; ans = mid;
        }
    }
    printf("%lld\n", ans);
    return 0;   
}

P3743 kotori的设备

#include <cstdio>
typedef long long LL;
const int MAXN = 100005;
const double EPS = 1e-6;
int n, p, a[MAXN], b[MAXN];
bool check(double x) {
    double r = p;
    for (int i = 0; i < n; ++i) {
        double t = 1.0 * b[i] / a[i];
        if (t < x) r -= 1.0 * a[i] - b[i] / x;
    }
    return r > -EPS;
}
int main() {
    scanf("%d%d", &n, &p);
    LL cost = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &a[i], &b[i]);
        cost += b[i];
    }
    if (cost <= p) {
        printf("-1\n");
        return 0;
    }
    double L = 0, R = 1e11;
    while (R - L > EPS) {
        double mid = (L + R) / 2;
        if (check(mid)) L = mid;
        else R = mid;
    }
    printf("%.6f\n", L);
    return 0;
}