题目
题目描述: 小咪是一个土豪手办狂魔,这次他去了一家店,发现了好多好多(n个)手办,但他是一个很怪的人,每次只想买k个手办。
而且他要让他花的每一分钱都物超所值,即:买下来的东西的总价值/总花费=max。请你来看看,他会买哪些东西吧。
多组数据。
第一行一个整数T,为数据组数。
接下来有T组数据。
对于每组数据,第一行两个正整数n,k,如题。
接下来n行,每行有两个正整数ci,vi。分别为手办的花费和它对于小咪的价值。
对于每组数据,输出一个数,即能得到的总价值/总花费的最大值。精确至整数。
解析
1)知识点
这道题就是一道简单的01分数规划,再运用二分。
2)看题目
这道题要求单位价值(题目中的总价值/总花费),我们假设单位价值为x,我们就可以知道,x = Σv / Σc。
3)算法分析
- 我们已经知道了这道题是要二分,那么我们就对单位价值进二分,也就是我们要求的答案。
- 由上面我们设立的公式:变式可以得到 Σv - Σc * x = 0。我们在二分猜测答案的时候就以这个为基准(为什么呢?看下面)。
- 如果我们选取的v和c使这个式子>0的话,说明至少还有一组v和c可以使得x更大:Σv - Σc * x > 0。这就是:x < Σv / Σc(算出了答案可以比二分猜测的x大)。
- 所以我们就可以依照这个式子得到每个物品的权值,然后进行排序,选出最大的k个。进行Σv - Σc * x > 0的判断。
4)算法操作
- 这里要进行二分,首先按模板上二分:
for (int i = 1; i <= 100; i++){ double mid = (l + r) / 2; if (judge(mid)) l = mid; else r = mid; } //这里用循环100次保证精度很高,不用<eps保证不会死循环
- 然后就是二分判断怎么写了。
- 按上面的说法,就是把Σb - Σa * x作为权值,从大到小排序,并进行k个统计判断就好了:
bool judge(double x) { for (int i = 1; i <= n; i++) w[i] = v[i] - x * c[i]; sort(w + 1, w + 1 + n, greater<double>()); double sm = 0; for (int i = 1; i <= k; i++) sm += w[i]; return sm > 0; }
5)打代码
- 所以我们先把c,v输入了。
- 然后二分猜测答案。
- 不断缩小范围,按照上面讲的二分判断进行判断。
- 下面全代码~
AC代码
#include <iostream> #include <algorithm> using namespace std; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //代码预处理区 const int INF = 0x3f3f3f3f; const int MAX = 1e4 + 7; int n, k; int c[MAX], v[MAX]; double w[MAX]; //全局变量区 bool judge(double x) { for (int i = 1; i <= n; i++) w[i] = v[i] - x * c[i]; sort(w + 1, w + 1 + n, greater<double>()); double sm = 0; for (int i = 1; i <= k; i++) sm += w[i]; return sm > 0; } //函数预定义区 int main() { IOS; int T; cin >> T; while (T--) { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> c[i] >> v[i]; double l = 0, r = INF; for (int i = 1; i <= 100; i++) { double mid = (l + r) / 2; if (judge(mid)) l = mid; else r = mid; } cout << (int)r << endl; } return 0; } //函数区