Antinomy与清理魔法

NC231156. Antinomy与清理魔法

描述

Antinomy拥有一个长度为 $\mathit n$ 由非负整数组成的数组 $\mathit a$ ，在一次使用魔法的过程中，可以选择两个不同的下标 $\mathit i$ 和 $\mathit j$ ，当 $\mathit a_i$ 和 $\mathit a_j$ 之间的绝对值不超过 $\mathit k$ 时，可以删除这两个元素中最小的一个，如果两个元素相等，可以消除其中的任何一个（只能删除一个）。Antinomy只是一个无情的魔法师工具人，希望你可以帮他判断他是否可以使用多次这个（可能为 $\text 0$ ）魔法来获得只剩下一个元素的数组。

输入描述

第一行两个整数 $n,k(1≤ n ≤ 5000,0≤ k ≤ 5000)$ --数组的长度,绝对值的最大上限

第二行 $\mathit n$ 个整数 $a_1,a_2...a_n(0≤ a_i ≤ 5000)$ ,其中 $\mathit a_i$ 是 $\mathit a$ 的第 $\mathit i$ 个元素

输出描述

输出共一行,如果数组可以只剩下一个元素，输出YES,否则输出NO

示例1

输入:

3 1
1 2 2

输出:

YES

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 5ms, 内存消耗: 424K, 提交时间: 2021-12-17 18:54:24

#include<bits/stdc++.h>
using namespace std;
int a[5001];
int main()
{
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	for(int i=2;i<=n;i++)
	{
		if(a[i]-a[i-1]>k)
		{
			cout<<"NO";
			return 0;
		}
	}
	cout<<"YES";
}

Python3 解法, 执行用时: 42ms, 内存消耗: 5160K, 提交时间: 2021-12-12 17:07:33

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
res=0
for i in range(1,len(a)):
    if a[i]-a[i-1]>k:
        res+=1
if res>2:
    print('NO')
else :
    print('YES')

上一题

下一题

详情