现在的位置: 首页 > 综合 > 正文

ural 1821. Biathlon

2012年03月29日 ⁄ 综合 ⁄ 共 1600字 ⁄ 字号 评论关闭

非常蛋疼的水题,基本上就是在考英文理解能力,题意灰常不好懂,看了讨论居然有英语国家的人也没理解题意,看来也不完全是本人英语理解能力不好。

搬上来翻译(来自刘树嘉):

冬天了一群小朋友在玩滑雪射击比赛。他们任意两个人出发的时间相差30秒。每个小朋友的到达时间与出发时间之差称为这位小朋友的比赛成绩。小朋友到达瞬间的比赛成绩比之前其他完成比赛的小朋友的比赛成绩都要好(时间短),则称该小朋友暂时领先。

现在给出n位小朋友以及每位小朋友的名字和到达时间,要求输出所有暂时领先的小朋友的名字。

数据保证任意两位小朋友的到达时间和比赛成绩都不同。

输入

第一行包括一个整数n(1 ≤ n ≤ 100),表示参赛小朋友的总数;

接下来n行,每行包括由一个空格隔开的两个字符串,第i行的第一个字符串表示第i个出发的小朋友的名字,第一个字母大写,后边的字母小写,名字长度不超过20个字节,第二个字符串表示该小朋友的到达时间,格式是“mm:ss.d”mm是分钟,ss是秒,d是秒数小数点后的一位。所有小朋友的名字都不相同。

输出

第一行输出所有暂时领先的小朋友的总人数;

接下来按照字典序,每行输出一个暂时领先的小朋友的名字。

 

看了老半天终于弄懂了,思路就很简单了:首先注意给出的时间并不是最终的finish_time,而是running_time,求finish_time要加上推迟的30*i。先对最终时间排序,然后扫描每一个人的running_time,如果他的

runningtime比前面所有的都小,就记录,最后按字典序排序输出。

 1 #include <iostream>
 2 #include <algorithm>        //for sort and min_element
 3 #include <vector>            //for vector<string>
 4 #include <string>
 5 using namespace std;
 6 struct Person
 7 {
 8     string name;
 9     double finish_time;
10     double running_time;
11 };
12 bool cmp(Person a, Person b)
13 {
14     return a.finish_time < b.finish_time;
15 }
16 bool cmp2(Person a, Person b)
17 {
18     return a.running_time < b.running_time;
19 }
20 int main()
21 {
22     int n;
23     scanf("%d", &n);
24     Person p[n];
25     double minute, second;
26     for (int i = 0; i < n; ++i)
27     {
28         cin >> p[i].name;
29         scanf("%lf:%lf", &minute, &second);
30         p[i].running_time = minute * 60 + second;
31         p[i].finish_time = p[i].running_time + 30 * i;
32     }
33     sort(p, p + n, cmp);                        //按finish_time排序
34     int num = 0;
35     vector<string> svec;
36     for (int i = 1; i <= n; ++i)
37     {
38         Person *it = min_element(p, p + i, cmp2);
39          if ((*it).running_time == p[i-1].running_time)      //判断当前p[i-1]是不是p[0]到p[i-1]最小的running_time
40         {
41             ++num;
42             svec.push_back(p[i-1].name);
43         }
44     }
45     sort(svec.begin(), svec.end());
46     printf("%d\n", num);
47     for (int i = 0; i < svec.size(); ++i)
48         cout << svec[i] << endl;
49     return 0;
50 }

 

抱歉!评论已关闭.