队列游戏

[编程题]队列游戏

热度指数：1312

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

算法知识视频讲解

小美最近发现了一种有趣的游戏，给定一个队列q，小美会按照以下规则进行游戏：

每次从队列中取出一个数，如果这个数是当前队列中最小的值，那么小美就会丢掉这个数。否则小美就会把这个数重新加入队列。

小美会一直进行游戏直到队列变空为止，但是小美并没有多少耐心，因此她想知道她最多需要进行多少次操作才能结束游戏。

输入描述:

第一行一个数n表示队列中数的个数。()

第二行n个数，第i个数ai表示队列中第i个被加进去的数的值。()

输出描述:

输出一个值表示小美需要操作的次数。

示例1

输入

5

6 4 2 1 3

输出

12

马上挑战

算法知识视频讲解

提交运行

算法知识视频讲解

添加笔记

求解答(88)

邀请回答

收藏(64)

分享

纠错

提交结果有问题?

8个回答

0篇题解

添加回答

6

不偷不抢安度因_

#include

using namespace std;

int main() {

int n;

cin >> n;

int cnt = n;

vector sorted(n), que(n);

for (int i = 0; i < n; ++i) {

int num;

cin >> num;

sorted[i] = que[i] = num;

}

sort(sorted.begin(), sorted.end(), [&](const auto& u, const auto& v) {

return u < v;

});

int idx = 0, start = 0;

while (idx < n) {

//auto it = find(que.begin() + start, que.end(), sorted[idx]);

//if (it == que.end()) {

// it = find(que.begin(), que.begin() + start, sorted[idx]);

//}

int it_idx;

for (it_idx = start; it_idx < que.size(); ++it_idx) {

if (que[it_idx] == sorted[idx]) {

break;

}

}

if (it_idx == que.size()) {

for (it_idx = 0; it_idx < start; ++it_idx) {

if (que[it_idx] == sorted[idx]) {

break;

}

}

}

//cnt += (it - que.begin() + 1);

//int it_idx = it - que.begin();

//if (it_idx < start) {

// cnt += (n - idx - start + it_idx);

//} else {

// cnt += (it_idx - start);

//}

cnt += ((it_idx - start + (int)que.size()) % (int)que.size());

start = it_idx;

que.erase(it_idx + que.begin());

//que.erase(it);

++idx;

}

printf("%d\n", cnt);

}

发表于 2021-03-03 14:51:49

回复(1)

5

听心zx

基本上所有模拟游戏过程的方法（有pop和push操作）的都会超时。 看了一楼大佬的代码，可以将序列想象成一个环，根据队列中最小值的位置与队列长度取模，得到的就是这个值需要几步才能从队列中移除，这样根据排好序的序列遍历一遍就可以把所有数需要移动的次数计算出来，不需要移动，或者说是只移动指针（改变索引）并不进行pop/push操作。

发表于 2021-03-19 10:04:35

回复(0)

2

SuLi-97

#include

#include

#include

using namespace std;

int main(){

int n;cin>>n;

vector> a(n,vector(2));

for(int i=0;i

cin>>a[i][0];

a[i][1] = i;

}

stable_sort(a.begin(),a.end());

vector dp;

int pre_index = 2000000000;

for(int i=0;i

int j=i,k=-1;

while(j

if(a[j][1]

k = j;

j++;

}

if (k==-1){

dp.back() += j-i;

pre_index = a[j-1][1];

}else{

if(dp.size()) dp.back() += j-(k+1);

dp.push_back(k-i+1);

pre_index = a[k][1];

}

i = j;

}

int length = dp.size();

int res = n*length--;

for (auto x :dp)

res -= x*length--;

cout<< res;

}

发表于 2021-03-07 01:25:38

回复(0)

1

hubblezhang

n = int(input())

que = list(map(int, input().split()))

que_sort = sorted(que)

count = 0

for a in que_sort:

for i in range(len(que)):

if que[i] == a:

count += i+1

break

que = que[i+1:] + que[:i]

print(count)

超时了

发表于 2023-03-08 23:03:21

回复(0)

0

JavaScript

一名24届求职者

const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; void (async function () { // Write your code here while (((line1 = await readline()), (line2 = await readline()))) { let number = parseInt(line1); let arr = line2.split(" ").map(Number); function queue(arr) { let fre = 0; while (arr.length > 0) { let isSmallest = true; for (let i = 1; i < arr.length; i++) { if (arr[0] > arr[i]) { let cur = arr[0]; for (let j = 0; j < arr.length - 1; j++) { arr[j] = arr[j + 1]; } arr[arr.length - 1] = cur; isSmallest = false; break; } } if (isSmallest) { arr.shift(); } fre++; } return fre; } console.log(queue(arr)); } })(); 超时

发表于 2023-05-26 14:14:00

回复(0)

0

print(1)

有没有大佬用python写出来的

发表于 2022-08-27 16:45:19

回复(1)

0

牛客971110286号

Num=input() N=int(Num) Line=input() L=[int(n) for n in Line.split()] Que=sorted(L) All_count=0 i=0 while i

发表于 2021-03-05 20:26:03

回复(2)

0

牛客912672316号

function getTimes(arr) { var times = 0; var flag = true; var k = 0; for (; arr.length != 0;) { for (var j = 1; j < arr.length - k; j++) { if(arr[0] > arr[j]) { arr.push(arr.shift()); times++; flag = false; break; } flag = true; } if (flag) { arr.shift(); times++; k = 0; } else { k++; } } console.log(times); return times; }

发表于 2021-02-24 19:44:39

回复(0)

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点