P2994 [USACO10OCT]吃晚饭的时候Dinner Time

    • 20通过
    • 57提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 排序 贪心 USACO 2010 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    【题目描述】

    农民约翰的$N$ $(1<=n<=1000)$头奶牛(编号为$1$~$n$ )在保加利亚参加IOI。奶牛们喜欢保加利亚的太阳,并享受他们的假期,一切似乎都很好。

    但是当晚餐时间时这发生了变化。由于餐厅很小,只有$M$ $(1 <= M <= N)$个牛的座位(编号$1$~$m$)。每头奶牛开始在一个坐标$(cx_i,cy_i)$ $(-1000000 <=cx_i≤1000000;-1000000≤ cy_i<= 1000000)$。他们可以在坐标$(sx_j, sy_j)$ $(-1000000 < = sx_j≤1000000;-1000000≤sy_j < = 1000000)$找到座位。

    奶牛有一个非常有效的(虽然很原始)的方法来分配座位。只要一头奶牛可以确定她会先坐到座位上,他会尽快地赶到那里(所有的奶牛都跑得一样快)。

    农民约翰的奶牛可以跳过座位、桌子、其他的牛,所以他们可以在一条直线上跑。当多个奶牛可以在同一时间达到一个座位,最老的牛(在输入数据中出现得早)将会得到座位。同样,当一头奶牛可以到达多个座位时,她也会选择最早在输入数据中出现的一个座位。

    有些牛不能吃晚饭(没有座位),那些饥饿的奶牛集体计划偷农民约翰的食物。农夫约翰想要一个他应该警惕的牛的名单。(在没有饥饿的奶牛的情况下,输出$0$)。你能帮他吗?

    【输入格式】

    第 $1$ 行:两个由空格隔开的整数$N$和$M$

    第 $2$ 至 $N+1$ 行:第 $I+1$ 行是两个由空格隔开的整数 $cx_i$ 和 $cy_i$

    第 $N+2$ 至 $N+M+1$ 行:第 $J+N+1$ 行是两个由空格隔开的整数 $sx_j$ 和 $sy_j$

    【输出格式】

    第 $1$ 至 $N-M$ 行是农夫约翰需要警惕的牛的编号,编号应该是从小到大的。

    【样例解释】

    第 $2$ 头牛:第一头刚开始在 $(0,1)$,第二头在$(1,0)$,只有 $(1,10)$ 有座位。

    第一头和座位之间的距离比第二头近,所以只有第一头能有座位。所以输出 $2$ 。

    感谢@__CDy 提供的翻译

    题目背景

    征求翻译。如果你能提供翻译或者题意简述,请直接发讨论,感谢你的贡献。

    题目描述

    Farmer John's N (1 <= N <= 1,000) cows conveniently numbered 1..N are participating in the IOI in Bulgaria. The cows like the Bulgarian sun and are enjoying their holiday. All seems well.

    This changes around dinner time. The restaurant is rather small, having only M (1 <= M <= N) cow seats conveniently numbered 1..M. Each cow starts at a location CX_i, CY_i (-1,000,000 <= CX_i <= 1,000,000; -1,000,000 <= CY_i <= 1,000,000); the seats can be found at SX_j, SY_j (-1,000,000 <= SX_j <= 1,000,000; -1,000,000 <= SY_j <= 1,000,000).

    The cows have a very efficient (though primitive) method to distribute themselves into the seats. As soon as a cow is certain she will get to a seat first, she rushes there as fast as she can (all cows runs equally fast).

    Farmer John's cows, like all prize cows, have no problem jumping over seats, tables, or other cows, so they can run in a straight line. When multiple cows can reach a seat at the very same time, the oldest cow (the one appearing earlier in the input data) gets the seat. Likewise, when a cow can be the first to reach multiple seats she will also choose the one appearing earliest in the input.

    Some cows won't be able to eat dinner, and those hungry cows are collectively planning to steal Farmer John's very own food. Farmer John would like a list of cows he should be wary of. (In the case when there are no hungry cows, output 0). Can you help him?

    NOTE: Standard distance calculations will likely require an

    intermediate result that will fit into a 64-bit integer but not into a 32-bit integer.

    农民约翰的N(1≤N≤1000)奶牛(编号1..N)在保加利亚参加IOI。奶牛们喜欢保加利亚的太阳,并享受他们的假期。一切

    似乎都很好。

    这在晚餐时间发生了变化。餐厅很小,只有M(1 <= M = N)个牛的座位(编号1 .. M).每头奶牛开始在一个位置

    cx_i,cy_i(1000000 <= cx_i≤1000000;1000000≤cy_i <= 1000000);可以在sx_j,sy_j

    (1000000 < = sx_j≤1000000;1000000≤sy_j < = 1000000)找到座位。

    奶牛有一个非常有效的(虽然很原始)的方法来分配座位。只要一头母牛可以确定她会先坐到座位上,她会尽快地

    赶到那里(所有的母牛都跑得一样快)。

    农民约翰的奶牛跳过座位、桌子、其他的牛不成问题,所以他们可以在一条直线上跑。当多

    个奶牛可以在同一时间达到一个座位,最老的牛(在输入数据中出现得早)将会得到座位。同样,当一头母牛可

    以到达多个座位时,她也会选择最早在输入数据中出现的一个。

    有些牛不能吃晚饭(没有座位),那些饥饿的奶牛集体计划偷农民约翰的食物。农夫约翰想要一个他应

    该警惕的牛的名单。(在没有饥饿的奶牛的情况下,输出0)。你能帮他吗?

    输入输出格式

    输入格式:

    * Line 1: Two space-separated integers: N and M

    * Lines 2..N+1: Line i+1 contains two space separated integers: CX_i and CY_i

    * Lines N+2..N+M+1: Line j+N+1 contains two space separated integers: SX_j and SY_j

    • 第一行:两个由空格隔开的整数N和M

    • 第二至N+1行:第I+1行是两个由空格隔开的整数cx_i和cy_i

    • 第N+2至N+M+1行:第J+N+1行是两个由空格隔开的整数sx_j和sy_j

    输出格式:

    * Lines 1..N-M: Line i contains the number of the ith cow that Farmer John should be wary of. The cow numbers should be listed in increasing order.

    • 第1至N-M行是农夫约翰需要警惕的牛的编号,编号应该是从小到大的。

    输入输出样例

    输入样例#1: 复制
    2 1 
    0 1 
    1 0 
    1 10 
    
    输出样例#1: 复制
    2 
    

    说明

    2 cows: Cow 1 starts at (0, 1) and cow 2 at (1, 0). There

    is only 1 seat at (1, 10).

    Cow 1 is closer to the seat than cow 2, so cow 1 will get the only seat.

    2头牛:第一头刚开始在(0,1),第二头在(1,0),只有(1,10)有座位。

    第一头和座位之间的距离比第二头近,所以只有第一头能有座位。所以输出2。

    感谢@PTC06 提供翻译

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。