AcWing 3321. ATM队列
原题链接
简单
算法(模拟)
思路:用一个双值数组或者用其他的储存容器(vector、set、map等等)储存2个值:取钱次数为主值,队列个人编号为次值,然后在进行排序时默认是按照第一个关键字(主值)进行排序。输出所有人离开队列的顺序时,取钱次数少的队列编号先输出,如果取钱次数相同的话,则按照它们刚开始在队列中的顺序进行输出。
set的排序时间复杂度为O(NlogN),而后续的查询、删除和插入等操作的时间复杂度为O(logN)
C++ 代码
#include<iostream>
#include<vector>
#include<queue>
#include<set>
using namespace std;
int main()
{
int t;
cin >> t;
set<pair<int,int>> mp; //set自动帮我们排序
for(int j = 1;j <= t;j++)
{
int n,k;
cin >> n >> k;
mp.clear(); // 清空mp,防止上一次循环遗留的数据影响当前循环
for(int i = 1;i <= n;i++) // 读入队列每个人的取钱数和队列编号
{
int x;
scanf("%d",&x);
mp.insert({(x-1)/k,i}); //(x-1)/k为x的取钱次数,因为当x<=k时都是取了一次钱就出队
//,x==k时要取两次钱才出队,以此类推,所有(x-1)/k为其取钱次数(0为取了一次
//钱,1为2次等等以此类推)
}
printf("Case #%d: ",j);
//输出出队顺序
for(auto item : mp)
{
cout << item.second << " ";
}
cout << endl;
}
return 0;
}