C++ 算法实现：最大化贴图图集得分

使用 C++ 解决贴图图集得分最大化问题

问题描述：

输入第一行一个正整数 n，表示一共有 n 张贴图，接下来的 n 行每行有两个正整数 w,s，w 为 2 的幂次表示正方形贴图的边长，s 表示贴图的权重，权重越大表示越重要。

输出图集最终得分 sum=贴图最终面积/贴图原始面积*贴图权重。输出一个数字，表示所有填充方式中，最大的图集得分。

思路：

将所有的贴图按照权重从大到小排序，然后依次将每个贴图放入已有的图集中，计算图集得分，取最大值即可。

代码实现：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

struct Texture {
    int w, s;
    double score;
};

bool cmp(Texture a, Texture b) {
    return a.s > b.s;
}

int main() {
    int n;
    cin >> n;
    vector<Texture> textures(n);
    for (int i = 0; i < n; i++) {
        cin >> textures[i].w >> textures[i].s;
        textures[i].score = textures[i].s * 1.0 / textures[i].w;
    }
    sort(textures.begin(), textures.end(), cmp);
    double maxScore = 0;
    int currW = 0, currS = 0;
    for (int i = 0; i < n; i++) {
        currW += textures[i].w;
        currS += textures[i].s;
        double currScore = currS * 1.0 / currW;
        maxScore = max(maxScore, currScore);
    }
    cout << fixed << setprecision(2) << maxScore << endl;
    return 0;
}

算法分析：

该算法首先根据权重对贴图进行排序，然后按照权重从大到小的顺序依次将贴图放入图集，并计算当前图集的得分。最后，算法返回所有填充方式中，最大的图集得分。

代码解释：

Texture 结构体用于存储贴图的信息，包括边长 w，权重 s 和得分 score。
cmp 函数用于对贴图按照权重进行排序。
main 函数首先读取输入数据，然后对贴图进行排序，并初始化当前图集的边长 currW 和权重 currS。
算法遍历排序后的贴图，依次将每个贴图放入图集，并计算当前图集的得分 currScore。
算法比较当前得分 currScore 和最大得分 maxScore，并将更大的值赋给 maxScore。
最后，算法输出最大得分 maxScore。

总结：

本算法使用 C++ 语言解决贴图图集得分最大化问题，通过将贴图按权重排序，依次放入图集并计算得分，最终输出最大得分。该算法的时间复杂度为 O(n log n)，其中 n 为贴图的数量。