11304: 【原1304】动量守恒

题目

题目描述

author: were 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1304

Description

时间限制：0.5s 空间限制：64MB

在一个长度为L m的平台上，放着N个质量相同的小球，每个小球的初始速度都为1m/s，

小球的运动方向按照摆上去的顺序间隔着向左或者向右，第一个摆上去小球的运动方向向右。

然后问题来了，小球我们认为小球的体积很小，

碰撞满足动量守恒定律，且发生完全弹性碰撞，碰撞不发生能量损失，碰撞的时间非常短暂可以忽略。

问平台上的第一个和最后一个小球分别是在什么时候掉下去的。

Input Format

输入共有两行。

第1行有2个整数，表示小球的数量N和平台的长度L。

第2行有N个整数，分别表示小球在平台上的位置，按照小球摆上去的顺序给出，平台的左端点位置为0，右端点位置为L。

保证开始的时候没有两个小球在一个位置。

Output Format

输出只有一行，两个整数。

分别表示小球最早掉下去的时间和最晚掉下去的时间。

Sample Input

5 10
1 3 5 7 9

Sample Output

1 9

Data Range

对于10%的数据，N,L<=10。

对于100%的数据，N<=10000，L<=1000000000，小球的位置在0..L之间。

鉴于前面几次机考总是有人写十个点各1s的暴力，为了节约大家反复提交进行评测的时间，特此0.5s。

skyzh's solution

#include <iostream>
using namespace std;

int main() {
    int N;
    long long L;
    long long T1 = -1, T2 = -1;
    cin >> N >> L;
    bool left = false;
    for (int i = 0; i < N; i++) {
        long long T;
        cin >> T;
        if (!left) T = L - T;
        left = !left;
        if (T1 == -1 || T < T1) T1 = T;
        if (T2 == -1 || T > T2) T2 = T;
    }
    cout << T1 << " " << T2 << endl;
}