今天看了优先队列问题,顺便水了两道题,嘿嘿,好久没写博客了,今天晚上回来,宿舍的那台大头机居然破天荒的能够连上网页,总结一下今天的收获……
下面是我看的关于优先队列资料:
在优先队列中,优先级高的元素先出队列。
标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。
优先队列的第一种用法,也是最常用的用法:
priority_queue<int> qi;
通过<操作符可知在整数中元素大的优先级高。
故示例1中输出结果为:9 6 5 3 2
第二种方法:
在示例1中,如果我们要把元素从小到大输出怎么办呢?
这时我们可以传入一个比较函数,使用functional.h函数对象作为比较函数。
priority_queue<int, vector<int>, greater<int> >qi2;
其中
第二个参数为容器类型。
第二个参数为比较函数。
故示例2中输出结果为:2 3 5 6 9
第三种方法:
自定义优先级。
struct node
{
friend bool operator< (node n1, node n2)
{
return n1.priority < n2.priority;
}
int priority;
int value;
};
在该结构中,value为值,priority为优先级。
通过自定义operator<操作符来比较元素中的优先级。
在示例3中输出结果为:
优先级 值
9 5
8 2
61
23
14
好吧,下面是我做的题目:
题目:坦克大战(貌似POJ上也有)
地址:猛击
代码如下:
时间:0ms 内存:660
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
struct node
{
int x,y,step;
};
struct cmp //定义优先级
{ bool operator()(node s,node t)
{
return s.step > t.step;
}
};
int map[301][301],shangxia[4]={0,0,1,-1},zuoyou[4]={1,-1,0,0};
int search(int x,int y)
{
int i,j,count=1;
node temp={x,y,count};
priority_queue<node,vector<node>,cmp> Q;
Q.push(temp);
while(!Q.empty())
{
Q.pop();
for(int k=0;k<4;k++)
{
i=x+zuoyou[k];
j=y+shangxia[k];
if(map[i][j]==4) return count;
if(map[i][j])
{
node r={i,j,count+map[i][j]};
Q.push(r);
map[i][j]=0;
}
}
count=Q.top().step;
x=Q.top().x;
y=Q.top().y;
}
return -1;
}
int main()
{
int x,y,i,j;
char str;
while(scanf("%d%d",&x,&y),x+y)
{
memset(map,0,sizeof(map));
for(i=1;i<=x;i++)
{
getchar();
for(j=1;j<=y;j++)
{
scanf("%c",&str);
if(str=='S'||str=='R')
map[i][j]=0;
if(str=='E')
map[i][j]=1;
if(str=='B')
map[i][j]=2;
if(str=='Y')
map[i][j]=3;
if(str=='T')
map[i][j]=4;
}
}
for(i=1;i<=x;i++)
for(j=1;j<=y;j++)
if(map[i][j]==3)
{
printf("%d\n",search(i,j));
break;
}
}
return 0;
}
题目:懒省事的小明
地址:请猛击
代码如下:
时间: 116ms 内存:308
#include<stdio.h>
#include<functional> //greater函数头文件
#include<queue>
using namespace std;
int main()
{
int ncase,n,i,temp,a,b,sum;
priority_queue<int,vector<int>,greater<int> >Q; //greater函数为比较函数见上面参考资料
scanf("%d",&ncase);
while(ncase--)
{
sum=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&temp);
Q.push(temp);
}
while(Q.size()!=1)
{
a=Q.top();
Q.pop();
b=Q.top();
Q.pop();
temp=a+b;
Q.push(temp);
sum+=temp;
}
Q.pop();
printf("%d\n",sum);
}
return 0;
}
好吧,知道近些天的积累,我才知道,不以AC为目的的做题,都是扯淡,好吧,以后要多多AC,多多,学习新知识,嘿嘿……
分享到:
相关推荐
适合新手,详情可见我博客
爬虫地址:https://code.csdn.net/youqi1shi/ojrobot/tree/master nyoj的所有题目,每个问题都转化成了单独的网页,没有其他零碎内容。
NYOJ离线版.chm、北大ACM题库、北大ACM题解答
双线程动态规划问题,很值得练习。传一个ac代码,测试一下csdn的功能。
算法-矩形嵌套(NYOJ-16)(包含源程序).rar
经典算法,最大单调递增子序列,查看最多能嵌入多少个矩形
字典树,Trie树,查找插入效率都很高的一种高级数据结构。
由于微信小程序没有方法可以获得当前用户所在城市的信息,所以需要调用方法来获取城市信息,用了两个方法去发送请求并返回城市信息 1. @Controller public class WechatLocationManager { private Logger logger ...
这个小程序的主要目的是为了用户用微信的用户信息登录后将用户信息授权存入自己的数据库中,这样以后每次微信登录得到的code 所得到的 openid 可以在项目的数据库中查到该用户的相关信息。 在测试的过程中,需要用户...
前期小程序开发只进行到根据微信用户登录获取的code 去微信的API去获取到该用户的openId和session_key,到了第二阶段,老大让我重写OAuthManager的代码来实现微信小程序和微信公众号平台获取用户信息的优化,即将...
南阳理工学院stl练习场全部ac代码!
南阳理工学院OJ第1版解题报告V1.0.pdf
给定一个由整数组成二维矩阵(r*c),现在需要找出它的一个子矩阵,使得这个子矩阵内的所有元素之和最大,并把这个子矩阵称为最大子矩阵。