POJ 2674 Linear world 题解 《挑战程序设计竞赛》 � 码农场

POJ 2674 Linear world

The Disc, being flat, has no real horizon. Any adventurous sailors who get funny ideas from staring at eggs and oranges for too long and set out for the antipodes soon learned that the reason why distant ships sometimes looked as though they were disappearing over the edge of the world was that they were disappearing over the edge of the world. (Terry Pratchett -Colour of Magic)
Not so long time ago people used to believe that they live on 2-D world and if they will travel long enough in one direction, they will fall down over the edge. Even when it was proved that the Earth is rounded some of them were still afraid to travel to the southern hemisphere.
Try to imagine one 1-D (linear) world. On such world there are only two possible directions (left and right). All inhabitants of such world were created exactly at the same time and suddenly all of them start to move (all with same constant velocity) in one or the other direction. If two inhabitants encounter each other, they politely exchange greetings and then they turn around and start to move in an opposite direction. When an inhabitant reaches the end of the world he falls away and disappears.
Your task is to determine, for a given scenario of creation, which inhabitant and when (counting from the moment of creation) will be the last one to fall away. You can assume that the time required to exchange greetings and turn around is 0.

Input

The input consists of multiple descriptions (data sets) of the creation moment. File structure is as follows:
N
LV
DIR POS NAME
...
The first line defines the number of inhabitants (N<32000). Data set starting with value N=0 represents the end of the input file. The second line contains length of the world L(float) and velocity of inhabitants V(float). Both values are always positive. In next N lines the data about inhabitants are given in an order of increasing POS (positive direction):
DIR – initial direction ('p' or 'P' for positive and 'n' or 'N' for negative)
POS – position in the time of creation (0<=POS<=L)
NAME – name of inhabitant (string up to 250 characters)
Input values within one line are separated with at least one space and there will be no empty lines in input. You may assume that input is always correct and that each data set has only one unique solution.

线性世界：一条线上N只蚂蚁，每只蚂蚁速度固定，方向和坐标不同，碰头后掉头，求最后掉下去那只蚂蚁的名字。

3.2常用技巧精选（一）

弹性碰撞

首先想象整个世界只有一只蚂蚁，于是可以计算出爬行时间最长的那一只，把它记下来。接着考虑其他蚂蚁，碰头时想象为两只蚂蚁交换姓名，擦肩而过即可。那么问题就剩下，统计这只蚂蚁跟多少只蚂蚁交换了姓名，最后交换的那一只就是答案了。那么到底跟谁交换了姓名呢？由于蚂蚁速度都一样，于是在前进路线上只会与那些逆行的蚂蚁碰头。统计出来后问题就解决了，需要注意答案的格式是截断小数不是四舍五入.

http://blog.163.com/scaulyd@126/blog/static/15522639520103124638816/
仍然考虑相遇和路过的问题。
先计算出如果是路过，那么是哪个人会最晚掉下去，那个人记为p。
首先你会发现相遇的两个人，必定从一开始就是相邻的。
然后，从头到尾，每个人路过了多少次呢？毫无疑问是在他方向上和他方向相反的人的个数k，即你会和所有和你方向相反的，且和你相面对而不是相背对的人相遇。
根据上面两个就可以发现，最晚掉下去的那个人，必定是从p向着他的方向数过去的第k个人。
至于原因。。。大概说起来是这个样子：
p路过k次，每一次路过就相当于p的下标加上或者减去1（视其方向而定）。这时候的p，就不是同样的一个人了，p只是一个假定的人而已。p的下标加减1就是p所指向的人，变成了原先和p相邻的右边或者左边那个人。

struct Inhabitant

{

    double position;

    string name;

    bool operator < (const Inhabitant& other) const

    {

        return abs(position) < abs(other.position);

    }

};

Inhabitant ih[MAX_N];

///////////////////////////SubMain//////////////////////////////////

int main(int argc, char *argv[])

{

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    int N;

    while (cin >> N && N)

    {

        double L, V;

        cin >> L >> V;

        for (int i = 0; i < N; ++i)

        {

            char pn;

            cin >> pn >> ih[i].position >> ih[i].name;

            if (pn == 'n' || pn == 'N')

            {

                ih[i].position = -ih[i].position;

            }

        }

        // 输入结束

        sort(ih, ih + N);

        double max_d = 0.0;  // 离端点的最远距离

        int id = 0;          // 对应的居民

        bool right = true;   // 该居民是否往右爬

        for (int i = 0; i < N; ++i)

        {

            double nd = (ih[i].position < 0.0 ? 0 : L) - ih[i].position;  // 离端点的距离

            if (nd > max_d + 1e-6)

            {

                max_d = nd;

                id = i;

                right = ih[i].position > 0.0;

            }

        }

        int count = 0;   // 该居民的前进路线上跟该居民反方向的个数

        if (right)

        {

            for (int i = id; i < N; ++i)

            {

                if (ih[i].position < 0.0)

                {

                    ++count;

                }

            }

            id += count;

        }

        else

        {

            for (int i = id; i >= 0; --i)

            {

                if (ih[i].position > 0.0)

                {

                    ++count;

                }

            }

            id -= count;

        }

        double result = max_d / V;

        cout << setw(13) << fixed << setprecision(2) << (int)(result * 100) / 100.0 << ' ' << ih[id].name << endl; // 这里是截断，不是四舍五入

    }

#ifndef ONLINE_JUDGE

    fclose(stdin);

    fclose(stdout);

    system("out.txt");

#endif

    return 0;

}

Also check http://even-eko.hatenablog.com/entry/2013/10/04/225623
Read full article from POJ 2674 Linear world 题解 《挑战程序设计竞赛》 � 码农场