POJ 3684

题目地址:http://poj.org/problem?id=3684

题目大意

用$N$个半径为$R$的小球做如下实验。

在$H$米高的位置设置了一个圆筒,将球垂直放入,最下面那个球最低点距离地面高度为$H$。实验开始时最下面的球开始掉落,此后每秒都会有一个球掉落。假设球与球和地面之间是弹性碰撞(速度交换)。

求出实验开始$T$秒后各个球的高度。假设重力加速度$g=10m/s^2$。

思路

首先一个球从高度$H$的地方掉落,需要的时间为
$$t=\sqrt{\dfrac{2 H}{g}}$$

那么可求得时刻$T$时球的高度$H$。($k=[\dfrac{T}{t}]$)

$$ y= \begin{cases} H-\dfrac{1}{2}g (T- kt)^2 & (k是偶数时,也就是球下落的时候) \\ H-\dfrac{1}{2}g ((k+1)t - T)^2 & (k是奇数时,也就是球上升的时候) \end{cases} $$

若不考虑半径$R$,那么球与球之间的碰撞可无视(穿过),求得各个时间段的球的高度排序一下即可。(因为球的顺序不变)

若考虑球的半径,则在原来不考虑半径的情况下加上$2Ri$(因为球在碰撞的时候下面的球直接“穿”过去少走了$2R$)

AC代码

/*************************************************************************
    > File Name: 3684.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-04 一 16:14:07 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int C;
int N, H, R, T;

const double g = 10; // 重力加速度10
double h[100+5];

double calc(int T) { // 计算T时刻小球的高度
    if(T<0) return H;
    double t = sqrt(2*H/g);
    int k = T/t;
    double d;
    if(k & 1) // 上升
        d = (k+1)*t - T;
    else // 下降
        d = T - k*t;
    return H-1/2.0*g*d*d;
}

void solve() {
    for (int i = 0; i < N; ++i) h[i] = calc(T-i);
    sort(h, h+N);
    for (int i = 0; i < N; ++i) printf("%.2f%c", h[i]+2*R*i/100.0, i==N-1?'\n':' ');
}

int main() {
#ifdef Oj
    freopen("3684.in", "r", stdin);
#endif
    cin >> C;
    while(C--) {
        cin >> N >> H >> R >> T;
        solve();
    }
    return 0;
}

POJ 3684

题目地址:http://poj.org/problem?id=2674

题目大意

在一个一维线性世界里,居民速度都相等并且只能往左或者往右移动,在居民们碰面的时候会互相打个招呼,然后各自转身掉头往相反方向移动,直到跌落线段边界。

现在给出线性世界长度$L$,以及居民们的速度$V$,和各个居民的移动方向$DIR$,坐标$POS$,名字$NAME$,问最后一个跌落世界的居民姓名以及时间。

思路

2333,把每个居民看做一直往一个方向移动,碰面就交换名字。

那么找出最后掉落的居民,求他前面有多少个与他反方向移动的,相对他的反方向居民偏移量就是最后一个名字。

AC代码

/*************************************************************************
    > File Name: 2674.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-04 一 17:27:45 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

int N;
float L, V;
struct inhabit {
    float pos;
    char name[255];
} inhabits[32000+5];

float maxL; // 最大距离
int maxI; // 最后一个掉落的居民


void solve() {
    int cnt=0; // 统计和最后掉下来那个居民相反方向的居民数量。
    if(inhabits[maxI].pos >= 0) { // 右边
        for(int i=maxI+1; i<N; ++i) if(inhabits[i].pos < 0) ++cnt;
    }
    else { // 左边
        for(int i=maxI-1; i>=0; --i) if(inhabits[i].pos > 0) --cnt;
    }

    printf("%13.2f %s\n", int(maxL/V*100.0)/100.0, inhabits[maxI+cnt].name); // 注意13是总长度而不是小数部分长度。
}

int main() {
#ifdef Oj
    freopen("2674.in", "r", stdin);
#endif
    char p;
    while(scanf("%d", &N) == 1) {
        if(N == 0) break;
        maxL = -1;
        float l;
        scanf("%f%f", &L, &V);
        for(int i=0; i<N; ++i) {
            getchar();
            scanf("%c%f%s", &p, &inhabits[i].pos, inhabits[i].name);
            if(p=='n' || p=='N') { // 这里没看到会有‘N'。。
                l = inhabits[i].pos;
                inhabits[i].pos = -inhabits[i].pos;
            }
            else l = L - inhabits[i].pos;

            if(maxL < 0 || maxL < l) {
                maxL = l;
                maxI = i;
            }
        }
        solve();
    }
    return 0;
}