首页 > 代码库 > bzoj4004 [JLOI2015]装备购买
bzoj4004 [JLOI2015]装备购买
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4004
【题解】
这种题目怎么这么眼熟呢?似乎这样的都能贪心。
按照物品价格从小到大排序,然后贪心插入。
插入的时候消元即可(线性基思想)
卡精度啊qwq
# include <math.h> # include <stdio.h> # include <string.h> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e2 + 10; const int mod = 1e9+7; # define RG register # define ST static int n, m; struct pa { ld a[M]; int v; friend bool operator<(pa a, pa b) { return a.v<b.v; } }p[M]; int cur[M]; int u, ans; int main() { scanf("%d%d", &n, &m); for (int i=1; i<=n; ++i) for (int j=1; j<=m; ++j) { int t; scanf("%d", &t); p[i].a[j] = (ld)t; } for (int i=1; i<=n; ++i) scanf("%d", &p[i].v); sort(p+1, p+n+1); for (int i=1; i<=n; ++i) { for (int j=1; j<=m; ++j) { if(fabs(p[i].a[j]) < 1e-8) continue; if(cur[j]) { ld r = p[i].a[j]/p[cur[j]].a[j]; for (int k=j; k<=m; ++k) p[i].a[k] -= r*p[cur[j]].a[k]; } else {cur[j] = i; ans += p[i].v; ++u;break;} } } printf("%d %d\n", u, ans); return 0; }
bzoj4004 [JLOI2015]装备购买
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。