01分数规划

那么

显然我们应该把最大的k个数放进去。单次复杂度n*log(n)；
可以接受
牛客上的题太坑l。。。。。。。。
https://loj.ac/problem/149

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
long long a[maxn], b[maxn], new1[maxn];
int n, m;
bool check(long long x) {
    priority_queue<long long> op;
    for (int i = 1; i <= n; i++) {
        op.push(a[i] - b[i] * x);
        //    cout<<a[i]-b[i]*x<<" ";
    }
    //    cout<<endl;
    long long now = 0, ans = 0;
    int t = n + 10;
    while (t--) {
        ans += op.top();
        op.pop();
        now++;
        if (now == m)
            break;
    }
    return ans >= 0;
}
int main() {
    // freopen("35.in","r",stdin);
    //    int t=1e9+10;
    // while(t--) {
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    scanf("%d%d", &n, &m);
    //    if(n==0&&m==0)
    //    break;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        a[i] *= 1e5;
    }
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &b[i]);
        // b[i]*=1e5;
    }
    long long ans3 = 0;
    int l = 1, r = 1e6 + 10;
    while (l <= r) {
        int mid = ((l + r) / 2);
        //    cout<<"mid="<<mid<<endl;
        if (check(mid)) {
            l = mid + 1;
            ans3 = mid;
        } else
            r = mid - 1;
    }
    double rr = 1e5;
    double ans1 = (double)ans3 / (double)rr;
    printf("%.04f\n", ans1 + 0.00000001);
    // printf("%.4f",0.69595+0.000001);
    // printf("%.4f",0.95955);
    return 0;
}

记得最后四舍五入的话，0.69995
在里面存的是0.69994999999999999999999999
所以不会四舍五入，这时候要加上一个较小的数。
T2
https://www.luogu.org/problem/P2115
锣鼓上的一道题，相当于bi是1.emmm好了。。。。。。。。

但是因为是连续的一段，所以需要维护一个最大子段和。然后看现在最小的行不行；

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6;
double a[maxn];
double b[maxn],need[maxn];
int n;
bool check(int x) {
    x=x;
    double x1=double(double(x)/100000);
    memset(need,-0x3f,sizeof(need));//不能是0，存在负数
    double sum=0;
    double ans1=need[0];
    for(int i=2; i<=n-1; i++) {
        need[i]=max(need[i-1]+(a[i]-x1),a[i]-x1);
        ans1=max(ans1,need[i]);
    }
    for(int i=1; i<=n; i++)
        sum+=(a[i]-x1);
    return sum-ans1<=0;
    //存在小于等于他的数 
}
int main() {
//freopen("1.in","r",stdin);
    cin>>n;
    double op;
    for(int i=1; i<=n; i++)
        cin>>a[i],op=max(op,a[i]);
    int l=1,r=int(op*100000);//可能出现必须取出一个的情况，这时候平均数大于总的平均数
    int ans=0;
    while(l<=r) {
        int mid=(l+r)/2;
        //    cout<<"mid="<<mid<<endl;
        if(check(mid)) {
            r=mid-1;
            ans=mid;
        } else {
            l=mid+1;
        }
    }
    //cout<<ans;
    printf("%.03f",double(ans)/100000+0.00000000001);
    return 0;
}

我真憨，真的。最后会有一个点会爆精度？？？？？？