Cheese 模拟，贪心（300）

题意 ：

• 有n种芝士，第i种芝士每克有$a_i$的价值，最多只能拿$b_i$克，问在最多拿w克的情况下，总的价值和最大是多少

思路 ：

• 贪心，从单位价值最高的拿起
• 对于每种芝士的数量限制，我们可以每次取min(w,b_i)，其中w是剩余可以用的克数
• 用vector而不用数组，减少空间
• 对vector进行输入时，用&，就可以了
• 对pair<int, int>进行排序，当需要从大到小，可以reverse

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <unordered_set> #include <math.h> #define endl '\n' #define fi first #define se second #define pb push_backusing namespace std; using ll = long long;typedef pair<int, int> PII;int main() {cin.tie(nullptr) -> sync_with_stdio(false);ll n, w; cin >> n >> w;vector<pair<long long, long long>> v(n);for (auto &nx : v)cin >> nx.fi >> nx.se;sort(v.begin(), v.end());reverse(v.begin(), v.end());ll ans = 0;for (auto &nx : v){ans += nx.fi * min(w, nx.se);w -= min(w, nx.se);}cout << ans << endl;return 0; }

总结

以上是生活随笔为你收集整理的Cheese 模拟，贪心（300）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。