队列游戏

[编程题]队列游戏

热度指数：1258 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

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

输入描述:

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

输出描述:

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

示例1

输入

5
6 4 2 1 3

输出

算法知识视频讲解

不偷不抢安度因_

#include <bits/stdc++.h>
  
using namespace std;
  
int main() {
    int n;
    cin >> n;
    int cnt = n;
    vector<int> 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)

听心zx

基本上所有模拟游戏过程的方法（有pop和push操作）的都会超时。

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

发表于 2021-03-19 10:04:35 回复(0)

SuLi-97

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n;cin>>n;
    vector<vector<int>> a(n,vector<int>(2));
    for(int i=0;i<n;i++){
        cin>>a[i][0];
        a[i][1] = i;
    }
    stable_sort(a.begin(),a.end());
    vector<int> dp;
    int pre_index = 2000000000;
     
    for(int i=0;i<n;){
        int j=i,k=-1;
        while(j<n && a[j][0]==a[i][0]){
            if(a[j][1]<pre_index)
                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)

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)

JavaScript

一名24届求职者

})();

超时

发表于 2023-05-26 14:14:00 回复(0)

print(1)

有没有大佬用python写出来的

发表于 2022-08-27 16:45:19 回复(1)

牛客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 <len(Que):
for j in range(len(L)):
inter=Que[i]
a=L[j]
if a==inter and i<len(Que):
i=i+1
count=j
L[j]='a'
All_count=len(L)+All_count

L=[L[i] for i in range(0,len(L)) if L[i]!='a']

print(All_count)

只能过前两个案例是为什么。。。。。

发表于 2021-03-05 20:26:03 回复(2)