C -Combination of Physics ans Maths

链接：https://ac.nowcoder.com/acm/contest/5671/C
来源：牛客网

题意：

给你一个n×m的矩阵，让你求去掉某些行和某些列后（可以不去行或列），矩阵内所有值的和/最后一行的和最大

solution：

由 推出 ad<bc
那么我们只要每次取每列的最大p，然后往那个最大的p上加入一些满足ad<bc关系的列，直到没有列能影响这个值了，记录最大值，然后去掉最后一行，循环前面的步骤

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
#define INF 0x3f3f3f3f

int t,n,m;
ll a[210][210],vis[210];
ll sum[210],big,di,k;
double maxn=0;
int main()
{

    cin>>t;
    while(t--)
    {
        scanf("%d%d",&n,&m);
        maxn=0;
        memset(sum,0,sizeof(sum));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                scanf("%lld",&a[i][j]);
                sum[j]+=a[i][j];
            }
        }
        for(int c=n-1;c>=0;c--)
        {
            k=0;
            for(int i=0;i<m;i++)
            {
                vis[i]=0;
                if(sum[k]*a[c][i]<sum[i]*a[c][k])
                    k=i;
            }
            vis[k]=1;
            big=sum[k];
            di=a[c][k];
            for(int i=0;i<m;i++)
            {
                if(vis[i])continue;
                if(big*a[c][i]<di*sum[i])
                {
                    big+=sum[i];
                    di+=a[c][i];
                    vis[i]=1;
                }
            }
            for(int i=0;i<m;i++)
                sum[i]-=a[c][i];
            double s=1.0*big/di;
            maxn=max(maxn,s);
        }
        printf("%.8f\n",maxn);
    }
    return 0;
}