试图用二分法解,除了三个点AC外全WA了。想问下哪里写错了
查看原帖
试图用二分法解,除了三个点AC外全WA了。想问下哪里写错了
4024
w2040w楼主2020/10/28 14:06
#include <set>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
//#define DEBUG
#define ll long long
#define MAX 100050
#define swp(x, y) int temp = x; x = y; y = temp
#define rep(i, init, n) for(int i = init; i < n; i++)
#define lowbit(i) ((i)&-(i))
using namespace std;
ll n = 0;
ll use[MAX], store[MAX];

int main(){
#ifndef ONLINE_JUDEG
    freopen("1.txt", "r", stdin);
#endif
    ll p;
    scanf("%d %lld", &n, &p);
    ll total = 0;
    rep(i, 0, n){
        scanf("%lld %lld", &use[i], &store[i]);
        total += use[i];
    }

    if(p >= total){
        printf("-1\n");
    } else {
        double l = 0, r = 1e10;
        while(r - l > 1e-6){
            double mid = (l+r) / 2;
            double sum = 0;
            rep(i, 0, n){
                if(mid*use[i] > store[i]){
                    sum += mid*use[i] - store[i];
                }
            }
            if(sum > mid*p){
                r = mid;
            } else{
                l = mid;
            }
        }
        printf("%.10lf\n", l);
    }
	return 0;

}

2020/10/28 14:06
加载中...