数据结构作业——buzhidao（队列）

2021-11-15 02:45:55

buzhidao

Description

有一个长度为 n 的序列，第 i 个数的大小为 a[i]。现在从第 1 个数开始从左往右进行以下操作：
1. 如果当前数是剩下的数中最大的，则输出并删去这个数。
2. 若不是，将它放到序列的末尾。
现在，bg 想知道一开始的第 m(从 1 开始计数)个数第几次被输出

Input

第一行输入两个正整数 n(0<n<=1000)、m(1=<m<=n)。接下去一行有 n 个正整数，第 i 个数表示 a[i]的值。

Output

输出一个数，表示第 m 个数第几次被输出。

Sample Input

5 21 2 3 4 56 12 2 8 2 2 2

Sample Output

思路

模拟这个插入删除过程，我们可以发现，第m个数要被输出，必须经过，左边比它大的数都输出，从右边起，找出右边第一个比它大的数，大于等于这个数都被输出，才能轮到第m个数被输出。

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1005;  

int main()
{
    //freopen("input.txt","r",stdin);
    int N,M,i,pos,cnt = 0,a[maxn];
    scanf("%d%d",&N,&M);
    for (i = 0;i < N;i++)    scanf("%d",&a[i]);
    for (i = 0;i < M - 1;i++)
    {
        if (a[i] >= a[M-1])  cnt++;
    }
    for (i = M;i < N;i++)
    {
        if (a[i] > a[M-1])
        {
            cnt++;
            pos = i;
            break;
        }
    }
    for (i = pos + 1;i < N;i++)
    {
        if (a[i] >= a[M-1])  cnt++;
    }
    printf("%d\n",++cnt);
    return 0;
}

码农公寓