2017年网站建设工作总结,局机关建设网站的意义,贵州 网站建设,网站更换服务器要重新备案吗题干#xff1a;
有N条鱼每条鱼的位置及大小均不同#xff0c;他们沿着X轴游动#xff0c;有的向左#xff0c;有的向右。游动的速度是一样的#xff0c;两条鱼相遇大鱼会吃掉小鱼。从左到右给出每条鱼的大小和游动的方向#xff08;0表示向左#xff0c;1表示向右…题干
有N条鱼每条鱼的位置及大小均不同他们沿着X轴游动有的向左有的向右。游动的速度是一样的两条鱼相遇大鱼会吃掉小鱼。从左到右给出每条鱼的大小和游动的方向0表示向左1表示向右。问足够长的时间之后能剩下多少条鱼Input第1行1个数N表示鱼的数量(1 N 100000)。
第2 - N 1行每行两个数A
ii, B
ii中间用空格分隔分别表示鱼的大小及游动的方向(1 A
ii 10^9B
ii 0 或 10表示向左1表示向右。Output输出1个数表示最终剩下的鱼的数量。Sample Input
5
4 0
3 1
2 0
1 0
5 0Sample Output
2解题报告用栈直接模拟十分简单。向右游的就入栈向左游的就依次判断出栈与否。如果栈为空并且来了一条往左游的鱼那就ans最后ans栈中元素的个数就是答案。本题亦可以直接模拟但是较繁琐有空可以一试。
ac代码
#includeiostream
#includecstdio
#includestackusing namespace std;
int main()
{stack int s;int n,x,d,flag;int ans0;int top0;scanf(%d,n);for(int i 1; in; i) {
// printf(\n****************************8\n) ;flag0;scanf(%d%d,x,d);if(s.empty() d0) {ans;}else if(s.empty()d1) {s.push(x);}else if( !s.empty() d1 ) {s.push(x);}else {while(!s.empty()) {tops.top();if(topx) {flag1;//表示向左游的这个鱼被吃掉了就是 这鱼不够大 不足以吃掉所有的鱼。 break; }else s.pop();}if(flag0) ans; } }printf(%d\n,s.size()ans);return 0 ;
}
