ZJU 3464 解题报告

Rugby Football

Time Limit: 2 Seconds Memory Limit: 65536 KB

CM is a member of Rugby football club of ZJU. He loves to play the game. Every Friday afternoon there is a club training of skills. CM wants to make it more effective.

In the training, N club members including CM stand at staring line in a row. The maximum velocity of the i-th player is Vi. The distance between the line and touchdown zone is L. The goal is to send the ball to touchdown zone. They can pass the ball to others but forward passing is illegal. If someone reaches touchdown zone with ball, the team scores and it will be an effective training.

This picture illustrate the rule of passing ball.

But the way to scoring is not easy because of crazy opponents. Any player with the ball cannot rush more than T seconds or he will be tackled. And he cannot be passed again because he will be very tired after sprinting; even have not for T seconds enough. At the beginning CM can choose who takes the ball first. Now CM wants to know whether they can score and how fast they can.

Input

The first line is an integer RP. Then RP cases follow. There are no more than 20 cases.

For each case, there are two lines. The first line contains three integers N, T, L (1 ≤ N,T ≤ 10000, 1 ≤ L ≤ 109). The second line has N integers indicating V1, V2 ... Vn. (1 ≤ Vi ≤ 10000)

Output

A single line with a float number S and correct to two decimal places. It means the total seconds they need to score. If they cannot score, output -1.

Sample Input

2
3 4 20
2 3 4
1 1 10
2

Output for Sample Input

5.33
-1

Author: HUANG, Minzhi

Contest: ZOJ Monthly, January 2011

浙大月赛的题目,除了这道大家都会做的,剩下的我暂时都不会.做这题花在读题上的时间比写代码的时间长的多得多.看来英语真的得好好念!

题目的意思很简单,有N个人,每个人跑步速度Vi,每个人只能跑T秒,问跑完L长距离所需的最少时间,保留两位小数.如果跑不完就输出-1.思路也很简单,谈心算法,按跑步速度排序,让跑得快的先跑就可以了!

CODE

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
 
bool cmp(int a, int b)
{
  return a > b;
}
 
int main()
{
  int rp;
  cin >> rp;
  int n, t, l;
  while(rp--)
    {
      cin >> n >> t >> l;
      int v[n];
      for(int i = 0; i < n; ++i)
        {
          scanf("%d", &v[i]);
        }
      sort(v, v + n, cmp);
      for(int i = 0; i < n; ++i)
        {
          if(l <= v[i] * t)
            {
              printf("%.2lf\n", t * i + 1.0 * l / v[i]);
              l = 0;
              break;
            }
          else
            {
              l -= v[i] * t;
            }
        }
      if(l) puts("-1");
    }
  return 0;
}
» 本博客采用署名 2.5 中国大陆许可协议进行许可,本文版权归作者所有,欢迎转载,但必须在明显位置给出原文连接。
anyShare分享到:
发表评论?

0 条评论。

发表评论

注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>