牛客 C-小猫排队 （模拟）

题目描述

世界上最苦恼的事情莫过于排队了，特别是排在你前面的猫比你可爱的时候。----《论猫的自我修养》

小猫啾啾现在就很苦恼，它排在队伍的末尾处等着买酱油，前面还有足足 只猫咪。但幸运的是小猫啾啾会一种魔法：它可以和前面距离它最近且比它可爱（可爱值大于啾啾）的小猫交换位置（被交换的小猫会被传送到啾啾之前的位置）。

已知啾啾每一分钟开始时可以施展一次魔法，而每一分钟过后排在队伍最前面的猫咪就会离开队伍（这意味这啾啾会先交换位置然后队伍才开始移动）。

因为等会还得去买饺子所以啾啾会尽可能地与自身前方比它可爱且未出队的小猫交换位置（可以证明交换后必定更快买到酱油），现在啾啾想请你帮它计算出它需要多久才能买到酱油离开。

输入描述:

第一行一个整数n代表啾啾前方小猫的数量。

第二行n个用空格隔开的整数代表从队伍最前方到队尾每只小猫的可爱值。

第三行一个整数代表啾啾的可爱值。

输出描述:

一行一个整数代表啾啾需要几分钟才能买到酱油离开队伍。

示例1

输入

6
9 7 3 7 6 2
5

输出

4

说明

用*表示啾啾的位置：

起始时：9 7 3 7 6 2 *（无人出队）

第一分钟时：7 3 7 * 2 6（9已出队）

第二分钟时：3 * 7 2 6（9 7已出队）

第三分钟时：* 7 2 6（9 7 3已出队）

第四分钟时：7 2 6（9 7 3 *已出队）

示例2

输入

1
5
2

输出

1

说明

第一分钟开始的时候啾啾就已经到了队首，所以在第一分钟结束时啾啾就会出队。

代码如下：

#include
using namespace std;
const int N = 2e5 + 10;
int n, t;
int a[N];int main() {ios::sync_with_stdio(false);cout.tie(nullptr);cin >> n;for(int i = 1; i <= n; i ++)  cin >> a[i];cin >> t;int r = n + 1, s = 1;for (int i = n; i >= s; i --) {if(a[i] > t) {  // 模拟整个过程s ++;       r = i;}}cout << r;  // r - s + 1 + s - 1 = r  发现运算结果最终就是 rreturn 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！