0pts求调
查看原帖
0pts求调
745929
Komeijizen楼主2025/1/22 16:10

rt,自己感觉挺对的,阳历也能过。。
难道这种枚举元逐个消掉的做法根本就是假的?

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

using db=double;
const db eps=1e-7;
const bool equ(double d1,double d2){
    return abs(d1-d2)<=eps;
}
const int N=505;
int n,m;db tmp;
struct mono{
    int cst;
    bool used=0;
    vector<db>prop;
    bool operator<(mono m1)const{
        return cst<m1.cst;
    }
}A[N];
int cnt,ans;
int main(){
    //File(1,1);
    cin>>n>>m;
    for(int i=1;i<=n;i++)A[i].prop.push_back(-114514);
    for(int i=1;i<=n;i++){
        for(int i=1;i<=m;i++){cin>>tmp,A[i].prop.push_back(tmp);}
    }
    for(int i=1;i<=n;i++)cin>>A[i].cst;
    sort(A+1,A+1+n);
    for(int i=1;i<=m;i++){
        int M=0;
        for(int j=1;j<=n;j++){
            if(!equ(A[j].prop[i],0.0) and !A[j].used){
                M=j;
                break;
            }
        }
        if(!M)continue;
        cnt++,ans+=A[M].cst,A[M].used=1;
        for(int j=1;j<=n;j++){
            if(equ(A[j].prop[i],0.0) or j==M)continue;
            db rt=A[j].prop[i]/A[M].prop[i];
            for(int k=1;k<=m;k++){
                A[j].prop[k]-=A[M].prop[k]*rt;
            }
        }
    }
    printf("%d %d\n",cnt,ans);
}
2025/1/22 16:10
加载中...