Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2458008
  • 博文数量: 392
  • 博客积分: 7040
  • 博客等级: 少将
  • 技术积分: 4138
  • 用 户 组: 普通用户
  • 注册时间: 2009-06-17 13:03
个人简介

范德萨发而为

文章分类

全部博文(392)

文章存档

2017年(5)

2016年(19)

2015年(34)

2014年(14)

2013年(47)

2012年(40)

2011年(51)

2010年(137)

2009年(45)

分类:

2010-01-15 11:35:06

Easy to Count
Submit: 194   Accepted:58
Time Limit: 1000MS  Memory Limit: 65535K
Description
There are N boxes on one straight line which is long enough.
They move at the same speed, but their directions may be different. That is, some boxes
may move left, while the others move right. As a beautiful girl fond of algorithm and
programming, Alice finds that two boxes moving toward each other will collide, and
after collision their directions change while their speeds remain the same. Alice also
knows that the boxes will not collide any more after many times of collision, she names
this final status as the stable status. The task is to help her count the number of
collisions before reach the stable status.


Input
here are multiple test cases. For each test case, the first line is an integer N (1 <= N <= 10000) representing the number of boxes, and the second line is N integers,
separated by spaces. The i-th integer will be -1 if the i-th box move left, otherwise,
it will be 1.
An negative integer indicates the end of input and should not be processed by your program.


Output
For each test case, output an integer which is the number of collisions to reach the
stable status on a single line in the format as indicated.


Sample Input

3
1 -1 1
4
1 -1 1 -1
-1


Sample Output

Case 1: 1
Case 2: 3


题意描述:
在一条无限长的直线上给定一组求,球的当前状态用1和-1来表示,1表示向右运动,-1表示向左运动,他们的运动速度是一样的。在两个球相撞之后各自转向,问经过多少次碰撞之后不再可能出现碰撞(称为稳态)。

在下面的情况下将出现稳态:
左边的球都向左运动,右边的球都向右运动,即出现-1 -1 ... -1 1 ...1 1 这种情况。

一个很简单的思路:可以把两个球相撞看作是它们穿过对方,那么问题转化为:只要求将1全部移到右边,需要穿越多少个-1即可。

#include <iostream>
using namespace std;

int main(int argc, char *argv[])
{
    int N, i, right, dir, ret, tcas = 1;
    while (cin >> N)
    {
        ret = right = 0;
        if (N < 0)
            break;
        for (i=0 ; i<N ; i++)
        {
            cin >> dir;
            if (dir > 0)
                right++;
            else
                ret += right;
        }
        cout << "Case " << tcas++ << ": " << ret << endl;
    }
}


阅读(644) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~