通过这道题,可以很好的学习和练习使用C++STL库中queue
和pair
的使用。
之前一直使用纯粹的C,有需要的地方就自己使用struct写链表等数据结构,因此排序、极值、哈希搜索等操作不仅写起来费事,而且效率不高,这一题彻底让我从之前纯粹使用C的方式转换成了使用C++和STL。
题目地址:http://codevs.cn/problem/5126/
关于优先队列priority_queue
和pair
,可以参考下面两篇比较全面的介绍:
优先队列priority_queue 详解
C++中pair的用法
值得注意的是,pair
不光做好了泛型,还做了operator<
的实现,因此可以默认通过priority_queue
进行最大堆的操作,而不需要自己写比较函数。
构建数据结构,distance距离位置,和value疲劳值。
将所有数据分为两个序列,左部lq和右部rq,分割点就在当前推销员所在的坐标位置(一开始坐标点在0点处),动态维护其坐标的变化。左部序列是一个大顶堆的优先队列,初始时为空;右部元素不必单独开辟,直接使用左边界哨兵控制区域位置即可。
(distance - nowDis) * 2 + value
值输出,同时记录目标元素的distance值,并将右部元素中所有小于等于此distance值的节点全部压入左部队列,压入权值为每个元素的value值。左部元素寻找最大值的方法:直接使用优先队列的特性,lq的top元素。
右部元素寻找最大值的方法:在rq中依次遍历,寻找最大的(distance - nowDis) * 2 + value
值
直到左部和右部序列全部为空,解题结束。
实际编码中,我并没有每次对比左部和右部的最大值,而是在开始时将右部元素全部整理压入左部队列,然后将左部队列依次输出即可。整理和压入的方法是:寻找到右部(distance - nowDis) * 2 + value
最大值后,将目标元素以(distance - nowDis) * 2 + value
权值入栈,其余distance小于等于目标元素distance的节点以value值入栈。这样程序显得简洁一点。
/**
* NOIP2015 推销员
* 学习使用pair泛型进行组合,而不需要自己写struct
* 学习使用priority_queue优先队列(默认为最大堆)
*/
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
int main()
{
//freopen("C:\\Users\\Administrator\\Desktop\\salesman\\salesman4.in","r",stdin);
//freopen("C:\\Users\\Administrator\\Desktop\\salesman\\salesman4-dd.out","w",stdout);
int N;
scanf("%d", &N);
pair<int, int> nodes[N];
for(int i = 0; i < N; i++){
scanf("%d", &nodes[i].second); //读入dis数据
}
for(int i = 0; i < N; i++){
scanf("%d", &nodes[i].first); //读入value数据
}
priority_queue< pair<int, int> > lq; //左部优先队列
int nowPos = 0, nowDis = 0, nowResult = 0, tempPos, tempMXPos, tempResult, tempMXResult;
//将nowPos不断向N逼近,迫使右部数据全部进入左部队列,最后整体输出左部队列
while(nowPos < N){
//找到本次登记的最大result和最大dis
tempMXResult = 0;
for(tempPos = nowPos; tempPos < N; tempPos++){
tempResult = (nodes[tempPos].second - nowDis) * 2 + nodes[tempPos].first;
if( tempResult >= tempMXResult ){
tempMXResult = tempResult;
tempMXPos = tempPos;
}
}
nowDis = nodes[tempMXPos].second;
//tempMXPos的权值为tempMXResult,其余小于nowDis的右部元素权值为first,将这些元素全部压入优先队列lq中
for(tempPos = nowPos; nodes[tempPos].second <= nowDis && tempPos < N; tempPos++){
if(tempPos == tempMXPos){
nodes[tempPos].first = tempMXResult;
}
lq.push(nodes[tempPos]);
}
nowPos = tempPos;
}
while(!lq.empty()){
nowResult += lq.top().first;
printf("%d\n", nowResult);
lq.pop();
}
return 0;
}