1 条题解
-
0
#include<bits/stdc++.h> using namespace std; // 存储每堆金币的信息:m-重量,v-价值 struct node{ int m,v; }arr[110]; // 比较函数:按单位价值(价值/重量)从高到低排序 // 贪心策略:优先拿单位价值高的金币,保证总价值最大 bool cmp(node a,node b){ return a.v*1.0/a.m > b.v*1.0/b.m; } int main(){ int n,t; cin >> n >> t; // [1] 输入金币堆数n和背包容量t // [2] 输入每堆金币的重量和价值 for(int i = 0; i < n; i++) cin >> arr[i].m >> arr[i].v; sort(arr, arr + n, cmp); // [3] 按单位价值降序排序金币堆 double sum = 0; // 记录可带走的最大总价值 // [4] 贪心选取金币:优先拿单位价值高的 for(int i = 0; i < n && t > 0; i++){ if(t >= arr[i].m){ // 背包容量足够,整堆拿走 sum += arr[i].v; t -= arr[i].m; }else{ // 背包容量不足,拿走当前堆的一部分 sum += t * (arr[i].v*1.0/arr[i].m); t = 0; } } cout << setprecision(2) << fixed << sum; // [5] 输出保留两位小数的总价值 return 0; }
- 1
信息
- ID
- 1035
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者