`
810364804
  • 浏览: 773304 次
文章分类
社区版块
存档分类
最新评论

11627 - Slalom (二分+贪心)

 
阅读更多

Problem E: Slalom

You are competing in a ski slalom, and you need to select the best skis for the race. The format of the race is that there areNpairs of left and right gates, where each right gate isWmetres to the right of its corresponding left gate, and you may neither pass to the left of the left gate nor to the right of the right gate. Theithpair of gates occurs at distanceyidown the hill, with the horizontal position of theithleft gate given byxi. Each gate is further down the hill than the previous gate (i.e.yi<yi+1for alli).

You may select fromSpairs of skis, where thejthpair has speedsj. Your movement is governed by the following rule: if you select a pair of skis with speedsj, you move with a constant downward velocity ofsjmetres per second. Additionally, at any time you may move at a horizontal speed of at mostvhmetres per second.

You may start and finish at any two horizontal positions. Determine which pair of skis will allow you to get through the race course, passing through all the gates, in the shortest amount of time.

Input Specification

The first line of input contains a single integer, the number of test cases to follow.

The first line of each test case contains the three integersW,vh, andN, separated by spaces, with 1 <=W<= 108, 1 <=vh<= 106, and 1 <=N<= 105.

The followingNlines of the test case each contain two integersxiandyi, the horizontal and vertical positions respectively of theithleft gate, with 1 <=xi,yi<= 108.

The next line of the test case contains an integerS, the number of skis, with 1 <=S<= 106.

The followingSlines of the test case each contain one integersj, the speed of thejthpair of skis, with 1 <=sj<= 106.

Sample Input

2
3 2 3
1 1
5 2
1 3
3
3
2
1
3 2 3
1 1
5 2
1 3
1
3

Output Specification

Output one line for each test case. If it is impossible to complete the race with any pair of skis, print the lineIMPOSSIBLE. Otherwise, print the vertical speedsjof the pair of skis that allows you to get through the race course in the shortest time.

Output for Sample Input

2
IMPOSSIBLE
题意:给定n个门和门的长度,n双滑雪板,求最大能通过所有门的滑雪板的速度。
思路:二分答案,然后去判断,判断的时候每次只要维护一个区间就可以了。
代码:
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int N = 100005;

int T, n, S, s[N * 10];
double w, v;
struct Sk {
    double s, e, y;
} sk[N];

void init() {
    scanf("%lf%lf%d", &w, &v, &n);
    for (int i = 0; i < n; i ++) {
	scanf("%lf%lf", &sk[i].s, &sk[i].y);
	sk[i].e = sk[i].s + w;
    }
    scanf("%d", &S);
    for (int i = 0; i < S; i ++)
	scanf("%d", &s[i]);
    sort(s, s + S);
}

bool judge(int sv) {
    double s = sk[n - 1].s, e = sk[n - 1].e;
    for (int i = n - 1; i > 0; i --) {
	double time = (sk[i].y - sk[i - 1].y) / sv;
	s = max(s - time * v, sk[i - 1].s);
	e = min(e + time * v, sk[i - 1].e);
	if (s > sk[i - 1].e || e < sk[i - 1].s || s > e)
	    return false;
    }
    return true;
}

void solve() {
    if (!judge(s[0])) {
	printf("IMPOSSIBLE\n");
	return;
    }
    int l = 0, r = S - 1;
    while (l < r) {
	int mid = (l + r)>>1;
	if (judge(s[mid])) l = mid + 1;
	else r = mid;
    }
    if (!judge(s[l]))
	l--;
    printf("%d\n", s[l]);
}

int main() {
    scanf("%d", &T);
    while (T--) {
	init();
	solve();
    }
    return 0;
}


分享到:
评论

相关推荐

    Pylon-course-slalom-test.zip_pylon_pylon labview_数据处理_数据采集 存储_汽车

    可实现汽车操纵稳定性中蛇行试验。包括数据采集,处理及存储的全过程。

    Slalom Ski Simulator-crx插件

    绕过大门完成赛道,并尝试改善每条赛道上的最佳时间! 篮球正在用绳子轻轻地摆动。 要得分扣篮,可以安排球的释放时间,使其恰好落入篮筐中。 你能制造多少个灌篮? 你的连胜纪录是什么?...特征:-无限级别,无限的...

    slalom:可信硬件中神经网络的快速,可验证和私有执行

    Slalom是一个框架,可通过有选择地将计算外包给不受信任(但速度更快)的托管设备,同时保留计算的完整性和私密性来加速受信任硬件中的深度神经网络评估。 在当前的实现中,Slalom对Intel SGX飞地内部的神经网络...

    slalom-experiments:http

    这是用于从 CLI 启动新的 reapp 应用程序的存储库。 当您运行命令reapp new时,它会被复制到一个新文件夹中。 要查看有关 reapp 的更多文档,请尝试。

    slalom-pesonal:开发组织

    激流回旋 开发组织

    论文研究 - 深度神经网络的完整性问题

    Hornik,Stinchcombe&White已显示具有足够隐藏层的多层前馈网络是通用逼近器。 Roux&Bengio已证明添加隐藏单元会严格提高建模能力,而受限玻尔兹曼机(RBM)是离散分布的通用近似器。 在本文中,我们提供了另一个...

    slalom:来自线性约束的声明式触摸交互

    有关更多信息,请查看当前状态Slalom 目前可用于制作简单的触摸交互原型以及学习线性约束和物理模拟。目标(短期优先) 使用更多交互和非触摸驱动动画(点击打开等)构建一些更深入的示例。 写一些真正的 API 文档...

    terraform-gcp-cloudfunction:为您的云功能提供GCP

    terraform-gcp-cloudfunction 工作中的cloudfunction模块和示例。用法将module.cloudfunction.tf添加到您的代码中:- module cloudfunction { source = " jameswoolfenden/cloudfunction/gcp " version = " 0.0.4 " ...

    qe-learning-roadmap:保留QE学习路线图的工件

    质量工程学习路线图该存储库包含QE学习路线图的公共版本。 只要注明作者姓名,就可以随意重用这些图像:“布莱克·诺里什(Blake Norrish)为激流回旋(Slalom Build)创建”

    movies_browser

    Slalom硅谷软件工程编码练习#04 一个使用AngularJS和Bootstrap的小型测试项目 有时,电影数据的加载速度可能很慢,因此请稍等片刻或刷新。 用户体验 电影海报的图像具有很强的关联性,可以使用户快速识别。 因此,...

    SlalomGenerator:相干激流回旋序列发生器-开源

    Slalom Generator 是用于生成序列的小型 Java 工具(跨平台)。 依次指出您知道的数字、绘图数量和预期的数字数量并生成!

    apphack-workshop:此仓库包含完成Apphack Terraform Workshop所需的文件!

    为了应对这一挑战,您将必须提供与活动期间与会人员相同的基础基础设施Slalom Build。如果时间允许,我们可能会提供一个教程供您参考此仓库,以配置您自己的基本基础结构。 我听说有Terraform的更高版本发布。我们会...

Global site tag (gtag.js) - Google Analytics