【NOIP2016提高A组五校联考1】挖金矿

Description

Solution

刚看到这题时，还在想怎么贪心，然后很快的打完之后发现贪心是错的。
然后仔细的看了看范围，哈哈，这不是二分吗。
二分出一个mid，然后在所有行里面用mid*j-前缀和然后找一个最大值。
最后把这些最大值加起来，判断一下就好了。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define rep(i,a) for(i=first[a];i;i=next[i])
using namespace std;
typedef long long ll;
int i,j,k,t,n,m,x;
double ans,o,da,ans1,p,shu,l,r,mid;
ll q,b[100007];
int de(int x,int y){return (x-1)*m+y;}
int main(){
// freopen("fan.in","r",stdin);
    scanf("%d%d",&n,&m);
    fo(i,1,n){
        q=0;
        fo(j,1,m){
            scanf("%d",&x);
            q+=x;
            b[de(i,j)]=q;
        }
    }
    l=0,r=1000000000;
    while(r-l>1e-5){
        mid=(l+r)/2;
        o=0;
        fo(i,1,n){
            da=-1000000000;k=0;
            fo(j,de(i,1),de(i,m)){
                k++;
                da=max(b[j]-mid*k,da);
            }
            o+=da;
        }
        if(o>=0)l=mid;else r=mid;
    }
    printf("%.4f\n",l);
}