当前位置:网站首页>ZCMU--1396: 队列问题(2)
ZCMU--1396: 队列问题(2)
2022-07-07 05:05:00 【小小小Why】
Description
有一个含有n个元素的队列q,每个元素的大小满足1<=xi<=9(0<i<n)。队列有一种操作,对于队首元素若是整个队列最大的则出队列,否则加入队尾。对于一个给定的m,你能告诉我xm是第几个出队列的吗?
Input
输入数据第一行是一个整数T(1<=T<=1000),表示输入数据的组数;每组数据的第一行是两正整数n表示队列的大小和第几个元素(1<n<=1000,0<=m<n),第二行有n个数xi ,分别代表每个元素的大小。
Output
对于每组测试数据,输出xm是第几个出队列。
Sample Input
3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1
Sample Output
1
2
5
解析:我们利用set来快速得出当前队列中最大元素值,因为有元素重复,所以我们得用multiset来存。我们可以用结构体来存元素的id和valu值,c表示第几个出列,如果a[ i ]==st.*rbegin()表示a[ i ]是当前队列中最大的元素,出列,如果是xm,那么就输出c即可,反之不是最大值,就到队尾,对应multiset中也要删除该元素,如此反复直到xm出列。
#include <stdio.h>
#include <set>
using namespace std;
struct su
{
int id;
int v;
}a[10005];
int main()
{
int t,i,n,k,c;
scanf("%d",&t);
while(t--){
multiset<int>st; //建立multiset
scanf("%d%d",&n,&k);
c=1; //表示第几个出列
for(i=0;i<n;i++){
scanf("%d",&a[i].v);
a[i].id=i;
st.insert(a[i].v); //存入set
}
for(i=0;i<n;i++){
if(a[i].v==*st.rbegin()){ //表示是当前队列最大值
if(a[i].id==k){ //刚好是xm
printf("%d\n",c);
break;
}else st.erase(--st.end()),c++; //删除最后一个元素,也就是最大值
}else{ //不是最大值,模拟到队尾
a[n].v=a[i].v;
a[n++].id=a[i].id;
}
}
st.clear();
}
return 0;
}
边栏推荐
- LeetCode中等题之我的日程安排表 I
- 2022年茶艺师(中级)考试试题及模拟考试
- 芯片资料 网站 易特创芯
- 【数字IC验证快速入门】14、SystemVerilog学习之基本语法1(数组、队列、结构体、枚举、字符串...内含实践练习)
- C language queue
- Linux server development, detailed explanation of redis related commands and their principles
- Recursive method constructs binary tree from middle order and post order traversal sequence
- 2022年全国最新消防设施操作员(初级消防设施操作员)模拟题及答案
- Lattice coloring - matrix fast power optimized shape pressure DP
- 青龙面板--整理能用脚本
猜你喜欢
MySQL multi column index (composite index) features and usage scenarios
追风赶月莫停留,平芜尽处是春山
Record a stroke skin bone error of the skirt
JS复制图片到剪切板 读取剪切板
2022 Inner Mongolia latest advanced fire facility operator simulation examination question bank and answers
快解析内网穿透助力外贸管理行业应对多种挑战
buureservewp(2)
【数字IC验证快速入门】12、SystemVerilog TestBench(SVTB)入门
2022茶艺师(初级)考试题模拟考试题库及在线模拟考试
LeetCode简单题之判断一个数的数字计数是否等于数位的值
随机推荐
Quickly use Jacobo code coverage statistics
The zblog plug-in supports the plug-in pushed by Baidu Sogou 360
Binary tree and heap building in C language
[quick start of Digital IC Verification] 15. Basic syntax of SystemVerilog learning 2 (operators, type conversion, loops, task/function... Including practical exercises)
运放电路的反馈电阻上并联一个电容是什么作用
【数字IC验证快速入门】10、Verilog RTL设计必会的FIFO
Most elements
The charm of SQL optimization! From 30248s to 0.001s
Cnopendata geographical distribution data of religious places in China
Leetcode 90: subset II
dash plotly
基于Pytorch 框架手动完成线性回归
微信小程序基本组件使用介绍
Linux server development, MySQL process control statement
【数字IC验证快速入门】17、SystemVerilog学习之基本语法4(随机化Randomization)
2022年全国最新消防设施操作员(初级消防设施操作员)模拟题及答案
2022茶艺师(初级)考试题模拟考试题库及在线模拟考试
力扣(LeetCode)187. 重复的DNA序列(2022.07.06)
Chip design data download
Minimum absolute difference of binary search tree (use medium order traversal as an ordered array)