bzoj4004 [JLOI2015]装备购买——线性基+贪心

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=4004

今天讲课讲到的题,据说满足拟阵的性质,所以贪心是正确的;

总之就贪心,按价格从小到大排序,不能被表出就买上,计入答案,然后去消别的;

看博客说要用 long  double,今天才第一次知道 long double 读入时是 %Lf 啊。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define eps 1e-6
using namespace std;
int const maxn=;
typedef long double ld;
int n,m,cnt,ans;
struct N{ld a[maxn]; int w;}t[maxn],p[maxn];
bool vis[maxn];
bool cmp(N x,N y){return x.w<y.w;}
void solve()
{
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
if(fabs(t[i].a[j])<eps)continue;
if(!vis[j])
{
vis[j]=;
p[j]=t[i];//j位置的装备
cnt++;
ans+=t[i].w;
break;
}
else//被消元
{
ld k=t[i].a[j]/p[j].a[j];
for(int l=;l<=m;l++)
t[i].a[l]-=k*p[j].a[l];
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%Lf",&t[i].a[j]);//%Lf!!
for(int i=;i<=n;i++)scanf("%d",&t[i].w);
sort(t+,t+n+,cmp);
solve();
printf("%d %d",cnt,ans);
return ;
}
上一篇:发送请求工具—Advanced REST Client的安装使用


下一篇:BZOJ4004 [JLOI2015]装备购买[贪心+线性基+高消]