莲花池 模拟题

题目来源：

2015中北大学‘计蒜客’杯新生赛

问题描述：

池子是细长条的，刚好有重量1~n的n条鱼，平时鱼儿们在池子里的相对位置不会改变，但是如果不按时喂它们，它们饿了就会吃仅比自己小一号的鱼。由于小鱼新陈代谢速度快，越小的鱼越早开始饿，也越早开始吃同类。算一下如果不给他们喂食算，最后还能剩下几条鱼。

输入描述

包含多组输入数据，每组数据占一行, 输入以0结束。每组开始输入一个正整数n(1≤n≤10^6 )表示原本池子里共有n条鱼，之后n个正整数a_1,a_2,…,a_n分别表示在池子里每条鱼的重量，保证每组数据中1≤a_i≤n，且鱼的重量互不相同。

输出描述

对于每组数据输出各占一行，每行一个正整数，表示该组最后剩下的鱼的总数。

样例输入

2 2 1
5 1 3 2 4 5
0

样例输出

1
2

提示

对于样例1，1号被2号吃掉，最后剩下1条鱼； 对于样例2，首先1号不能被吃掉，然后2号被3号吃掉，紧接着3号被4号吃掉，再然后4号被5号吃掉，最后剩下1号和5号共2条鱼。

分析

用一个数组id[i]记录重量为i的鱼的位置，用结构体来维护鱼的相对位置关系。越小的鱼越早开始饿，那么从小到大模拟一下就行了。

代码

#include 
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
int id[maxn];
struct node{int m,r,l;
}a[maxn];
int n;
int main(){while(scanf("%d",&n)&&n){for(int i=1;i<=n;i++){int x;scanf("%d",&x);id[x]=i;a[i]=node{x,i+1,i-1};}int ans=n;for(int i=2;i<=n;i++){int p=id[i];if(a[p].l>0&&a[p].m==a[a[p].l].m+1){a[p].l=a[a[p].l].l;a[a[p].l].r=p;ans--;}else if(a[p].r<=n&&a[p].m==a[a[p].r].m+1){a[p].r=a[a[p].r].r;a[a[p].r].l=p;ans--;}}printf("%d\n",ans);}return 0;
}

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