AT_abc477_b.Standing Outliers
入门
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There are N people on a number line. The people are numbered 1 to N, and person i is at coordinate Xi. Multiple people may be at the same coordinate.
A person is said to "stand apart" if their distance to every other person is at least D.
Formally, person i is said to "stand apart" if ∣Xi−Xj∣≥D holds for all j (1≤j≤N, j=i).
Output the numbers of all people who "stand apart" in ascending order.
数轴上有 N 个人。这些人编号为 1 到 N,其中第 i 个人位于坐标 Xi 处。多个人可能位于同一坐标。
若某个人到其余所有人的距离均不小于 D,则称该人“独立站立”。
形式化地,当对所有 j(满足 1≤j≤N 且 j=i)均有 ∣Xi−Xj∣≥D 成立时,称第 i 个人“独立站立”。
请按升序输出所有“独立站立”之人的编号。
输入格式
The input is given from Standard Input in the following format:
N D
X1 X2 … XN
输入从标准输入中按以下格式给出:
N D
X1 X2 … XN
输出格式
Let K be the number of people who stand apart, and let (P1,P2,…,PK) be the sequence of their numbers sorted in ascending order. Output them in the following format:
K
P1 P2 … PK
If K=0, the second line should be empty.
设 K 为独自站立的人数,(P1,P2,…,PK) 为其编号按升序排列后的序列。请按以下格式输出:
K
P1 P2 … PK
若 K=0,则第二行应为空。
输入输出样例
输入#1
3 3 1 5 7
输出#1
1 1
输入#2
3 2 1 1 1
输出#2
0
输入#3
8 3 4 77 20 26 9 26 22 40
输出#3
4 1 2 5 8
说明/提示
Sample 1 Explanation:
Person 1 has distance 4 to person 2 and distance 6 to person 3, so their distance to every other person is at least D. Thus, person 1 "stands apart".
Person 2 has distance 2 to person 3, so person 2 does not "stand apart".
Similarly, person 3 has distance 2 to person 2, so person 3 does not "stand apart" either.
Thus, only person 1 "stands apart".
Sample 2 Explanation:
There may be people at the same coordinate. Also, if no one "stands apart", the second line should be empty.
Sample 3 Explanation:
Output the numbers of the people who "stand apart" in ascending order.
Constraints
- 2≤N≤100
- 1≤D≤109
- 1≤Xi≤109
- All input values are integers.
样例 1 解释:
第 1 个人到第 2 个人的距离为 4,到第 3 个人的距离为 6,因此其到其他所有人的距离均不小于 D。故第 1 个人“独立于众人”。
第 2 个人到第 3 个人的距离为 2,因此第 2 个人不“独立于众人”。
同理,第 3 个人到第 2 个人的距离也为 2,因此第 3 个人也不“独立于众人”。
综上,仅有第 1 个人“独立于众人”。
样例 2 解释:
可能存在位于同一坐标的多人。此外,若无人“独立于众人”,则第二行应为空行。
样例 3 解释:
按升序输出所有“独立于众人”的人的编号。
约束条件
- 2≤N≤100
- 1≤D≤109
- 1≤Xi≤109
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?