C. Weight of the System of Nested Segments
发布时间
阅读量：
阅读量
蒟蒻 在写(补)完cf div3的题后来水一篇题解
题目
问题的大致意思是给一系列对应点及其权重值，请选择两个点使得它们的权重之和最小。
思路
本题的核心考点在于贪心算法与排序技术。解题思路较为直观，在具体实现上较为直接。具体而言，在算法设计阶段需要构建一个映射表来存储坐标与其对应的权重关系，并且需要注意输入坐标的顺序问题。由于每个坐标的值都是独一无二的特性，在数据处理过程中可将其作为映射表的关键字进行操作。特别地，在输出结果时需确保前一个区间严格包含后一个区间的逻辑条件得到满足才能完成最终结果的有效性验证。
难点
我认为本题的关键点在于如何实现按value大小对map进行排序。我在查看相关资料时参考了网上的博客后才掌握这一技巧，并在此过程中学到了很多新知识。直接调用sort函数也无法按value大小对map进行排序。因此，我们采用了一种新的方法：创建一个pair类型的一维向量，并对该向量进行排序；随后，在原有算法中将所有的map操作替换为使用该向量的相应操作。
实现代码如下：
#include <bits/stdc++.h>
#define inf 0x7fffffff
#define ll long long
#define mod 1000000007
using namespace std;
map<int, int> Weight; //储存坐标对应权重
map<int, int> Coordinate; //储存坐标输入的顺序
//注意这里要传入地址，否则不会改变传入值的顺序
bool cmp(pair<int, int> &a, pair<int, int> &b)
{
return a.second < b.second;
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
Weight.clear();
Coordinate.clear();
int n, m, a, b;
scanf("%d %d", &n, &m);
int i, sum = 0;
for (i = 1; i <= m; i++)
{
scanf("%d %d ", &a, &b);
sum += b;
Weight[a] = b;
Coordinate[a] = i;
}
//将map传入vetor
vector<pair<int, int>> Weight_vec(Weight.begin(), Weight.end());
//对vetor进行排序
sort(Weight_vec.begin(), Weight_vec.end(), cmp);
//逐个删除最大的权重，同时更新sum
while (Weight_vec.size() > 2 * n)
{
auto it = Weight_vec.end();
it--;
sum -= it->second;
Coordinate.erase(it->first);
Weight_vec.erase(it);
}
printf("%d\n", sum);
//配对输出
//每次输出第一个和最后一个坐标来满足输出的要求
for (i = 1; i <= n; i++)
{
auto it1 = Coordinate.begin();
auto it2 = Coordinate.end();
it2--;
printf("%d %d\n", it1->second, it2->second);
Coordinate.erase(it1->first);
Coordinate.erase(it2->first);
}
printf("\n");
}
system("pause");
return 0;
}评测结果
全部评论 (0)
还没有任何评论哟~