51Nod 1289 大鱼吃小鱼(模拟,经典好题)

时间:2023-03-09 08:26:31
51Nod 1289 大鱼吃小鱼(模拟,经典好题)
            题目来源:             Codility                    
基准时间限制:1 秒 空间限制:131072 KB 分值: 5        
难度:1级算法题
           
有N条鱼每条鱼的位置及大小均不同,他们沿着X轴游动,有的向左,有的向右。游动的速度是一样的,两条鱼相遇大鱼会吃掉小鱼。从左到右给出每条鱼的大小和游动的方向(0表示向左,1表示向右)。问足够长的时间之后,能剩下多少条鱼?
Input
第1行:1个数N,表示鱼的数量(1 <= N <= 100000)。
第2 - N + 1行:每行两个数A[i], B[i],中间用空格分隔,分别表示鱼的大小及游动的方向(1 <= A[i] <= 10^9,B[i] = 0 或 1,0表示向左,1表示向右)。
Output
输出1个数,表示最终剩下的鱼的数量。
Input示例
5
4 0
3 1
2 0
1 0
5 0
Output示例
2
题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1289
分析:
模拟一下,对于第i条鱼,如果方向朝右,用一个数组去记录此时的鱼的大小,当存在向左的鱼的时候,让这向左游动的鱼与此鱼去比较,如果C[flag]<w[i],那么flag死,flag--;继续去访问flag前面的值,否则i死,继续去访问i+1之后的元素
下面给出AC代码:
 #include <bits/stdc++.h>
using namespace std;
int main()
{
int w[];
int t[];
int C[];
int T;
while(scanf("%d",&T)!=EOF)
{
for(int i=;i<=T;i++)
scanf("%d%d",&w[i],&t[i]);
int m=T;
int flag=-;
for(int i=;i<=T;i++)
{
if(t[i]==)
C[++flag]=w[i];
else
{
while(flag!=-)
{
m--;
if(C[flag]<w[i])
flag--;
else break;
}
}
}
printf("%d\n",m);
}
return ;
}