蓝桥艺术学院有编号1到n的n名舞者,每个舞者都有两个属性, 分别是美丽值ai和气质值bi。作为学院的老师,你需 要选择不超过k人参加市区的舞蹈比赛。一个团队的美丽值为团队 成员的美丽值的和乘以团队成员气质值的最小值,即 minbi.∑ai,其中S表示团队中的成员集合。请问你能组成的最 ieS ies 大的团队美丽值是多少?给出c++代码
时间: 2024-03-18 10:41:45 浏览: 11
以下是使用贪心算法的 C++ 代码实现:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
struct Dancer {
int beauty;
int charm;
};
bool cmp(const Dancer &a, const Dancer &b) {
return a.charm < b.charm;
}
int main()
{
int n, k;
cin >> n >> k;
Dancer dancers[n];
for (int i = 0; i < n; i++) {
cin >> dancers[i].beauty >> dancers[i].charm;
}
sort(dancers, dancers + n, cmp);
long long maxBeauty = 0;
for (int i = 0; i < k; i++) {
maxBeauty += dancers[i].beauty * (long long)dancers[i].charm;
}
long long beauty = 0;
for (int i = 0; i < k; i++) {
beauty += dancers[i].beauty * (long long)dancers[k - 1].charm;
}
maxBeauty = max(maxBeauty, beauty);
cout << maxBeauty << endl;
return 0;
}
```
其中,我们首先定义一个 `Dancer` 结构体,表示每个舞者的美丽值和气质值。然后,我们将所有舞者按照气质值从小到大排序,并依次选择前 k 个舞者计算团队美丽值,取其中的最大值。
需要注意的是,由于美丽值和气质值都可能非常大,因此在计算团队美丽值时需要使用长整型,即 `(long long)dancers[i].beauty * dancers[i].charm`,以避免溢出。