Easy to CountSubmit: 194 Accepted:58Time Limit: 1000MS Memory Limit: 65535KDescription
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
-1Sample 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;
}
}
|
阅读(648) | 评论(0) | 转发(0) |