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

---

解题思想

---

/* 根据分析：俩个鱼会有4个状态，分别是 0,0 0,1 1,0 1,1 根据分析：只有1,0这种情况才有可能被吃掉（前吃后，或者，后吃前都有可能） 发现，这很像括号匹配，1相当于左括号，0相当于右括号， 于是便想到了用数据结构栈， 上面只是总体思路，但是实现换种方式：假设当前栈底总是放着1(左括号)，是1就入栈，是0就分俩种情况，一种1吃0， 一种是0吃1，不管如何0都不入栈，只是对总数进行-1， 为什么这样做呢？应为上面说了，吃与被吃只有1,0，才有可能，所以我们栈中只存放1的鱼，对于遇到0的鱼，比较一下，能不能被吃掉，或者吃掉1. */

---

代码

---

import java.util.Scanner; import java.util.Stack; public class Main { private static class Yu { private int weight; private int flag; public Yu(int w, int f) { weight = w; flag = f; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // init Yu[] yu = new Yu[n]; Stack<Yu> stack = new Stack<>(); // input for (int i = 0; i < n; ++i) yu[i] = new Yu(sc.nextInt(), sc.nextInt()); // process int sum = n; //sum鱼的总数 for (int i = 0; i < n; ++i) { if (yu[i].flag == 0) { while (!stack.isEmpty()) { //0吃1 if (yu[i].weight > stack.peek().weight) { stack.pop(); sum--; } else { //1吃0，这里一定要break //因为栈里面装的全是1，不然会 //死循环 sum--; break; } } } else { stack.push(yu[i]); } } System.out.println(sum); // for (Yu y : stack) // System.out.println(y.weight + " " + y.flag); } }