题解|装备购买题解

真正意义上的线性基...在关于向量加法和标量乘法的线性空间中的线性基。题目的意思就是要构造一个价格最低的基底。对于同个线性空间它的基底的位数不会变，那么要费用最低，可以按费用排序然后依次加入线性基判定是否可行。
关于证明，设该线性空间中的向量为 $A$ ，线性基中的向量为 $B$ ，若存在 $(b_1,b_2,...,b_|B|)$ 满足， $A_k=b_1B_1+b_2B_2+..+b_|B|B_|B|$ ，而A_k是费用最低的一个向量，显然可以对于任意一个 $p(p\leq |B|)$ ，使得 $B_p=(b_1B_1+b_2B_2+..+b_|B|B_|B|-b_pB_p+A_k)/(-b_p)$ ，那么就相当于用 $A_k$ 代替 $B_p$ 成为线性基中的一个元素，线性基的位数不变，可表出的向量不变。而总费用更低。所以这么贪心是正确的。

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const long double eps = 1e-6;
const int N = 510;

int vis[N];
int n, m, ans, tot;
struct Node {
    int c;
    long double p[N];
} a[N];
bool operator < (Node a, Node b) {
    return a.c < b.c;
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            double tmp;
            scanf("%lf", &tmp);
            a[i].p[j] = tmp;
        }
    }
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i].c);
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(fabs(a[i].p[j]) > eps) {
                if(vis[j]) {
                    long double rate = a[i].p[j] / a[vis[j]].p[j];
                    for(int k = 1; k <= m; ++k) 
                        a[i].p[k] -= rate * a[vis[j]].p[k];
                } else {
                    ans += a[i].c; 
                    ++tot;
                    vis[j] = i;
                    break;
                }
            }
        }
    }
    printf("%d %d\n", tot, ans);
}