例如,给定数组A={1,3,2,17,10}
,答案是3
,因为集合{1,2,3}
是最大的集合,因此对于集合中的某些a
,集合中的每个元素都是范围[a, a + 4]
(包括a+4
)。
我的算法就像
int[] toys = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
Array.Sort(toys);
int max_together = 0;
for(int i = 0; i < toys.Length; ++i)
{
int plus_four = toys[i] + 4;
int j = i + 1;
for(; j < toys.Length && toys[j] <= plus_four; ++j);
int span = j - i;
if(span > max_together)
{
max_together = span;
}
}
并且大多数测试用例都失败了。
或者我可能读错了https://www.hackerrank.com/challenges/priyanka-and-toys?h_r=next-challenge&h_v=zen…
完整的解是
using System;
using System.Collections.Generic;
using System.IO;
class Solution
{
static void Main(String[] args)
{
Console.ReadLine(); // N
int[] toys = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
Array.Sort(toys);
int max_together = 0;
for(int i = 0; i < toys.Length; ++i)
{
int plus_four = toys[i] + 4;
int j = i + 1;
for(; j < toys.Length && toys[j] <= plus_four; ++j);
int span = j - i;
if(span > max_together)
{
max_together = span;
}
}
Console.WriteLine(1 + (toys.Length - max_together));
}
}
快速查看,我发现您正试图找到排序数组的最大跨度(即:1,2,3,10,17),而测试用例希望您找到给定数组的最大跨度(即。1、3、2、17、10),排序前的那个
如果您购买1个重量为w1的玩具,您将免费获得重量在[w1,w1+4]之间的所有玩具。这个问题要求你找到你需要购买的最小玩具数量,这样你就能得到输入中的所有玩具。在这个例子中,A={1,3,2,17,10},答案是3,因为你需要购买玩具1(或2或3),17和10。
Java代码int num[] = {1,3,2,17,10};
Arrays.sort(num);
int result=1;
int lastToy=num[0];
for(int i=1;i<n;i++)
{
if(num[i] > lastToy+4)
{
result++;
lastToy= num[i];
}
}