警钟超烂
查看原帖
警钟超烂
995117
pineappler楼主2024/1/19 16:28

如果你在个别点错误,可能是精度问题,这道题的精度十分玄学,使用 double 情况下,EPS 的值选择 10−510^{-5} 到 22(是的你没看错)都可以通过本题。大部分情况下开 long double 都能过。

吐槽数据,建议加强。

AC 代码:

#include <bits/stdc++.h>
using namespace std;
const long long N=505;
const double EPS=2;
struct line{
	double a[N];
	long long w;
};
line G[N];
bool cmp(line a,line b){
	return a.w<b.w;
}
bool st[N];
long long cnt;
int main(){
	long long n,m;
	scanf("%lld%lld",&n,&m);
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=m;j++){
			scanf("%lf",&G[i].a[j]);
		}
	}
	for(long long i=1;i<=n;i++){
		scanf("%lld",&G[i].w);
	}
	sort(G+1,G+n+1,cmp);
	long long ans=0;
	for(long long i=1;i<=n;i++){
		long long t=1;
		while(t<=m && (fabs(G[i].a[t])<EPS || st[t])){
			t++;
		}
		if(t>m) continue; 
		st[t]=true;
		ans+=G[i].w;
		cnt++;
		for(long long j=i+1;j<=n;j++){
			double v=G[j].a[t]/G[i].a[t];
			for(long long k=1;k<=m;k++){
				G[j].a[k]-=G[i].a[k]*v;
			}
		}
	}
	printf("%lld %lld",cnt,ans);
	return 0;
}
2024/1/19 16:28
加载中...