装备购买（实数线性基）

装备购买

哈哈，这才是真正的线性基呀！跟线性代数里面学的一模一样！

题意：

求给定矩阵的秩，并且所选的基底尽可能小（“小”的定义在题面中）

思路：

1. 像平时做的二进制线性基一样插入即可
2. 插入前按照 $c$c的值先排个序，就当做贪心了吧
3. （补充：如果所有条件全部换成整数，而不是实数，则不能当做线性基处理。比如将此处的 $m$m维换成 $1$1维，那么这个问题就变成背包问题了，比如货币系统）

题面描述

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 5e2+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-6; //这里改成1e-10反而WA了两个点！！！

struct P{
    long double mat[maxn];
    int c;
    long double & operator [] (const int x) { return mat[x]; }
    friend bool operator < (const P &a, const P &b) { return a.c<b.c; }
}a[maxn];

int n, m, cnt, ans, p[maxn];

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    n=read(), m=read();
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j) scanf("%Lf", &a[i][j]);
    for(int i=1; i<=n; ++i) a[i].c=read();
    sort(a+1,a+1+n);
    for(int i=1; i<=n; ++i) {
        for(int j=1; j<=m; ++j) if(fabs(a[i][j])>eps) {
            if(!p[j]) { cnt++, ans+=a[i].c, p[j]=i; break; }
            long double t=a[i][j]/a[p[j]][j];
            for(int k=j; k<=m; ++k) a[i][k]-=t*a[p[j]][k];
        }
    }
    printf("%d %d\n", cnt, ans);
}