2018牛客网暑假ACM多校训练赛（第五场）A gpa(01分数规划)

ゝ一世哀愁。 2021-09-16 00:36 223阅读 0赞

关于01分数规划，可以学习这篇博客，画了图之后就非常好懂了。  
[%一下，orz][orz]  
回到这题，我们需要的wi=si∗ci−si∗L  w i = s i ∗ c i − s i ∗ L (假如你不懂我在说什么，请看上面的blog）  
然后这里我用二分写的

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){
       if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
    //head//
    const int maxn = 1e5+10;
    #define eps 1e-7
    struct num
    {
        int s,c;
    } t[maxn];
    double w[maxn];
    int n,k;
    int main()
    {
        scanf("%d%d",&n,&k);
        rep(i,0,n)
        {
            scanf("%d",&t[i].s);
        }
        rep(i,0,n)
        {
            scanf("%d",&t[i].c);
        }
        double l,r,mid;
        l = 0;
        r = 1000.0;
        while(l - r < (-1) * eps)
        {
            mid = (l+r)/2;
            rep(i,0,n)
            {
                w[i] = t[i].s*t[i].c - t[i].s * mid;
            }
            sort(w,w+n);
            double ans = 0;
            rep(i,k,n)
            {
                ans += w[i];
            }
            if(ans >= 0)
            {
                l = mid;
            }
            else
                r = mid;
        }
        printf("%.6f",mid);
    }

附一个学到的**精度误差处理方式**   
设ε为精度误差，越小精度越高，如ε=10−8，程序中经常将它写为eps=1E-8  
减少精度误差的方法：  
a=b⇔|a−b|<ε  a = b ⇔ | a − b | < ε   
a<b⇔a−b<−ε  a < b ⇔ a − b < − ε   
a≤b⇔a−b<ε  a ≤ b ⇔ a − b < ε   
第三个想了一下才明白，由前两个推出来的  
|a−b|<ε⇔a−b<ε,a−b>−ε  | a − b | < ε ⇔ a − b < ε , a − b > − ε   
a−b<−ε  a − b < − ε   
两个求并集就行了

[orz]: https://blog.csdn.net/hzoi_ztx/article/details/54898323