V - 大鱼吃小鱼

有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个数，表示最终剩下的鱼的数量。

Sample Input

Sample Output

思路：

一开始我的思路是

首先

两条鱼（注意x轴是不封闭的）

0 0是不会遇到问题的。

0 1也不会遇到问题

1 1也不会遇到问题

1 0会遇到问题

所以我们就先把所有的小鱼，用一个class，保存每一条小鱼的方向和大小。

然后每找到一条小鱼的方向是1，就向右遍历，如果下一条小鱼也是1，那么我们就跳出遍历。

如果下一条小鱼是0，那就看能不能吃，吃了的话就继续遍历，不能就跳出遍历，然后设大小为0（被吃了）

但是这个算法有一个问题

8 1

2 0

3 1

4 0

这样子算，我们最后的答案会是两条，因为我们的8 1小鱼吃不到4 0小鱼

所以我就换了个思路！

每次存小鱼的时候，我们就看小鱼方向是不是0，如果是的话，就向前面的遍历，找方向为1的小鱼

能吃就吃，被吃的大小变0，不能吃就自己的大小为0。

上代码！

#include<iostream>
using namespace std;
class Fish
{
public:
int m_size;
int m_dir;
};
int main()
{
Fish *arr = new Fish[100000];
int n = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> arr[i].m_size >> arr[i].m_dir;
if (arr[i].m_dir == 0)
{
for (int k = i - 1; k >= 0; k--)
{
if (arr[k].m_dir == 1 && arr[k].m_size < arr[i].m_size)
arr[k].m_size = 0;
if (arr[k].m_dir == 1 && arr[k].m_size > arr[i].m_size)
{
arr[i].m_size = 0;
break;
}
}
}
}
int sum = 0;
for (int i = 0; i < n; i++)
{
if (arr[i].m_size > 0)
sum++;
}
cout << sum << endl;
delete[]arr;
arr = NULL;
}

秒客网

V - 大鱼吃小鱼

相关文章