题解 | #[SCOI2010]传送带#

错误思路

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
struct item
{
	int cost;
	int value;
	double vc;
};
struct cmp {
	bool operator()(const item& a, const item& b) const {
		return a.vc > b.vc;
	}
};
void solve() {
	int n, k;
	cin >> n >> k;
	vector<item> items;
	for (int i = 0;i < n;i++) {
		item temp;
		cin >> temp.cost;
		cin >> temp.value;
		temp.vc = (double)temp.value / temp.cost;
		items.push_back(temp);
	}
	sort(items.begin(), items.end(), cmp());
	int sumcost = 0;
	int sumvalue = 0;
	for (int i = 0;i < k;i++) {
		sumvalue += items[i].value;
		sumcost+= items[i].cost;
	}
	double ans = (double)sumvalue / sumcost;
	cout << (int)ans << endl;
 }
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

想当然的认为按照value/cost进行排序，然后直接相加 其实当输入的值为
1
3 2
1 100
300 100
4 1
的时候，这个方法就肯定是不对的
这个时候选择1 100和4 1的手办结果最大，而不是1 100和300 100这两个手办
所以就需要修正一下思路，使用如下代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
struct item
{
	int cost;
	int value;
	double vc;
};
struct cmp {
	bool operator()(const item& a, const item& b) const {
		return a.vc > b.vc;
	}
};
vector<item> items;
int n, k;
bool check(double mid) {
	for (auto& i : items) {
		i.vc = i.value - i.cost * mid;
	}
	sort(items.begin(), items.end(), cmp());
	double ans = 0;
	for (int i = 0;i < k;i++) {
		ans += items[i].vc;
	}
	return ans > 0;
}
void solve() {
	cin >> n >> k;
	for (int i = 0;i < n;i++) {
		item temp;
		cin >> temp.cost;
		cin >> temp.value;
		items.push_back(temp);
	}
	double l = 0;
	double r = INT_MAX;
	for (int i = 0;i < 1000;i++) {
		double mid = (l + r) / 2;
		if (check(mid)) {
			l = mid;
		}
		else {
			r = mid;
		}
	}
	cout << (int)r << endl;
	items.clear();
 }
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

成功AC！！！\