yxy

用户名：dotcpp0787179

访问量：445

签　名：

竞赛交流论坛： blog.qzcy2.top 欢迎来撩！

等　　级
排　　名	1030
经　　验	3291
参赛次数	1
文章发表	23
年　　龄	1
在职情况	学生
学　　校	内江师范学院
专　　业	纳西妲系

　　自我简介：

我不会

TA的其他文章

[金银岛]自定义排序优先'均权'最大--我看题解都太复杂辣
浏览：48

杀到这九天十地无人敢称尊,直到身边再无一人能陪我征战,叶天帝不过如此
浏览：23

你可能喜欢

A+B for Input-Output Practice (VI) （C++代码）

[金银岛]自定义排序优先'均权'最大--我看题解都太复杂辣

　　作者: yxy　　　　发表时间：2024-10-20 23:38:49 浏览：48　|　评论：1　

原题链接：金银岛

# 贪心 自定义排序找均权值最大

#### 好久没发题解了。。。

##### 核心思路：通过价值/重量 得到单位价值 
###### 按照单位价值从大到小得顺序装 直到装不下为止
##### **金属可切割
###### 若装不下整个金属 那么就能装多少装多少 按照 价值/重量 * 能装下得重量

###### AC Code：
```cpp
#include <iostream>   
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <map>

#define int long long
using namespace std;
const int N = 11000;
//map<double , double> m;   
typedef pair<double , double> PII;  //自定义双精浮点数对组

bool cmp(PII x , PII y)  //比较权值 从大到小
{
    double temp1 = x.second / x.first , temp2 = y.second / y.first;
    return temp1 > temp2;
}

PII a[N];		//数据存贮数组
inline void solve()
{
    int t;
    cin >> t;
    while ( t -- )
    {  
        double w;
        int s;
        cin >> w >> s;
        for (int i = 1 ; i <= s ; i ++ ) 
            cin >> a[i].first >> a[i].second;

sort(a + 1 , a + 1 + s , cmp);

// for (int i = 1 ; i <= s ; i ++ )
        // { 
        //     printf ("%.2f %.2f \t" , a[i].first , a[i].second);
        //     printf ("%.2f\n" , a[i].second / a[i].first);
        // }

// printf ("\n");
        double ans = 0;
        int i = 1;
        while (w - a[i].first >= 0 && i <= s)  //这里只讨论能装下的情况的最大价值
        {
            ans += a[i].second;
            w -= a[i].first;
            i ++;
            // printf ("%.2f \n" , ans);
        }

if (w != 0 && i <= s)  //若上一步还没有装完 并且 背包还有空的情况
        {
            double temp = w / a[i].first;  //能装多少是多少
            temp *= a[i].second;
            ans += temp;
        }

printf("%.2f\n" , ans);

}
    return ;
}

signed main()
{
    ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);  //超级加速！
    solve();
    return 0;
}
```

//祝大家早日ac 比赛ak 给蒟蒻留下一个小小的赞把！

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

yxy

(≧▽≦)/(≧▽≦)/(≧▽≦)/ (≧▽≦)/(≧▽≦)/(≧▽≦)/

2024-10-21 00:36:02

yxy

TA的其他文章

你可能喜欢

单词个数统计（C++代码）

C二级辅导-公约公倍（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

矩形面积交（Java代码）

A+B for Input-Output Practice (VI) （C++代码）

[金银岛]自定义排序优先'均权'最大--我看题解都太复杂辣

评论区

精彩推荐

不容易系列（C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

校门外的树（C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

C语言训练-大、小写问题（C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

1162答案错误，为什么

A+B for Input-Output Practice (II) （C语言代码）

yxy

TA的其他文章

你可能喜欢

单词个数统计 （C++代码）

C二级辅导-公约公倍 （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

矩形面积交 （Java代码）

A+B for Input-Output Practice (VI) （C++代码）

[金银岛]自定义排序优先'均权'最大--我看题解都太复杂辣

评论区

精彩推荐

不容易系列 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

校门外的树 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

C语言训练-大、小写问题 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

1162答案错误，为什么

A+B for Input-Output Practice (II) （C语言代码）

单词个数统计（C++代码）

C二级辅导-公约公倍（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

矩形面积交（Java代码）

　　评论区

不容易系列（C语言代码）

校门外的树（C语言代码）

C语言训练-大、小写问题（C语言代码）