我得到了集合 {1, 2, 3, ... ,N}。我必须找到给定集合的子集的最大大小，以便子集中的任何 2 个数字的总和不能被给定的数字 K 整除。N 和 K 可以达到 2*10^9，所以我需要一个非常快的算法。我只想出了一个复杂度为 O(K) 的算法，它很慢。
问问题
5989 次
5 回答
5
首先计算所有集合元素 mod k。并解决简单的问题：找到给定集合的子集的最大大小，使得子集中的任何 2 个数字的总和不等于给定数字 K。我划分这个集合到不能同时选择 set(i) 和 set(ki) 的两组（i 和 ki）。
int myset[]
int modclass[k]
for(int i=0; i< size of myset ;i++)
{
modclass[(myset[i] mod k)] ++;
}
选择
for(int i=0; i< k/2 ;i++)
{
if (modclass[i] > modclass[k-i])
{
choose all of the set elements that the element mod k equal i
}
else
{
choose all of the set elements that the element mod k equal k-i
}
}
最后，您可以从元素 mod k 等于 0 或 k/2 中添加一个元素。
这个解决方案的算法复杂度为 O(K)。
您可以使用动态数组改进这个想法：
for(int i=0; i< size of myset ;i++)
{
x= myset[i] mod k;
set=false;
for(int j=0; j< size of newset ;j++)
{
if(newset[j][1]==x or newset[j][2]==x)
{
if (x < k/2)
{
newset[j][1]++;
set=true;
}
else
{
newset[j][2]++;
set=true;
}
}
}
if(set==false)
{
if (x < k/2)
{
newset.add(1,0);
}
else
{
newset.add(0,1);
}
}
}
现在你可以选择复杂度为 O(myset.count) 的算法。你的算法比 O(myset.count) 更多，因为你需要 O(myset.count) 来读取你的集合。该解决方案的复杂度为 O(myset.count^2)，您可以根据输入选择算法。比较 O(myset.count^2) 和 o(k)。为了获得更好的解决方案，您可以根据 mod k 对 myset 进行排序。
于 2012-12-22T11:55:33.793 回答
4
我假设对于某些 N，数字集始终是 1 到 N。
考虑前 N-(N mod K) 个数。K 个连续数的形式 floor(N/K) 序列，从 0 到 K-1 减少 mod K。对于每个组，必须删除 floor(K/2) 以获得归约 mod K，它是 floor(K/2) 的另一个子集的否定 mod K。您可以从每组 K 个连续数字中保留上限（K/2）。
现在考虑剩余的 N mod K 数。他们从 1 开始减少 mod K。我还没有计算出确切的限制，但如果 N mod K 小于 K/2 左右，您将能够保留所有这些限制。如果没有，您将能够保留其中的第一个上限（K/2）。
==================================================== =========================
我相信这里的概念是正确的，但我还没有弄清楚所有的细节。
==================================================== =========================
以下是我对问题的分析和答案。在接下来的 |x| 是地板（x）。此解决方案类似于@Constantine 的答案中的解决方案，但在某些情况下有所不同。
考虑第一个 K*|N/K| 元素。它们由 |N/K| 组成 减少模 K 的重复。
一般来说，我们可以包括|N/K| k 模 K 的元素受到以下限制：
如果 (k+k)%K 为零，我们可以只包含一个 k 模 K 的元素。这就是 k=0 和 k=(K/2)%K 的情况，这只能发生在偶数 K 中。
这意味着我们得到 |N/K| * |(K-1)/2| 重复的元素。
我们需要纠正省略的元素。如果 N >= K 我们需要为 0 mod K 元素加 1。如果 K 是偶数且 N>=K/2，我们还需要为 (K/2)%K 个元素加 1。
最后，如果 M(N)!=0，我们需要添加重复元素的部分或完整副本 min(N%K,|(K-1)/2|)。
最终公式为：
|N/K| * |(K-1)/2| +
(N>=K ? 1 : 0) +
((N>=K/2 && (K%2)==0) ? 1 : 0) +
min(N%K,|(K-1)/2|)
这与@Constantine 的版本不同，在某些情况下甚至涉及 K。例如，考虑 N=4，K=6。正确答案是 3，即集合 {1, 2, 3} 的大小。@Constantine 的公式给出 |(6-1)/2| = |5/2| = 2. 上面的公式前两行各取 0，第三行取 1，最后一行取 2，给出正确答案。
于 2012-12-22T09:59:00.347 回答
3
公式是
|N/K| * |(K-1)/2| + ost
ost =
if n<k:
ost =0
else if n%k ==0 :
ost =1
else if n%k < |(K-1)/2| :
ost = n%k
else:
ost = |(K-1)/2|
在哪里 |a/b| 例如 |9/2| = 4 |7/2| = 3
例如 n = 30 , k =7 ;
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30
1 2 3 |4| 5 6 7. - 是第一行。8 9 10 |11| 12 13 14 - 第二行如果我们在每行中获得前 3 个数字，我们可能会获得该子集的大小。我们也可以从 (7 14 28) 中添加一个数字
获得前 3 个数字 (1 2 3) 是一个数字 |(k-1)/2| . 这一行的编号是|n/k| . 如果没有剩余，我们可以添加一个数字（例如最后一个数字）。如果残差 < |(k-1)/2| 我们得到最后一行的所有数字，否则得到|(K-1)/2|。
感谢例外情况。ost = 0 如果 k>n
于 2012-12-22T10:26:12.697 回答
0
这是对 ABRAR TYAGI 和 amin k 解决方案的解释。
该解决方案的方法是：
- 创建一个包含 K 个桶的数组 L，并将输入数组 D 中的所有元素分组到 K 个桶中。每个桶 L[i] 包含 D 的元素，使得 ( element % K ) = i。
- 所有能被 K 整除的元素都在 L[0] 中。所以只有这些元素中的一个（如果有的话）可以属于我们的最终（最大）子集。这些元素中的任何两个之和都可以被 K 整除。
- 如果我们将 L[i] 中的一个元素添加到 L[Ki] 中的一个元素，那么总和可以被 K 整除。因此，我们可以仅将这些桶中的一个元素添加到我们的最终集合中。我们选择最大的桶。
代码：d 是包含大小为 n 的初始数字集的数组。这段代码的目标是找到 d 的最大子集的计数，使得没有两个整数之和可以被 2 整除。
l 是一个包含 k 个整数的数组。这个想法是将数组d中的每个（元素）减少到（元素％k）并保存它们在数组l中出现的频率。
例如 l[1] 包含所有元素的频率 % k = 1
我们知道 1 + (k-1) % k = 0 因此必须丢弃 l[1] 或 l[k-1] 以满足没有两个数字 % k 之和应为 0 的标准。
但由于我们需要 d 的最大子集，我们选择 l[1] 和 l[k-1] 中的较大者
我们遍历数组 l 使得 for (i=1; i<=k/2 && i < ki; i++) 并执行上述步骤。
有两个异常值。l[0] 组中任意两个数字的总和 % k = 0。因此，如果 l[0] 非零，则加 1。
如果 k 是偶数，则循环不处理 i=k/2，并使用与上述相同的逻辑将计数加一。
于 2016-12-07T21:46:37.537 回答
0
n,k=(raw_input().split(' '))
n=int(n)
k=int(k)
l=[0 for x in range(k)]
d=[int(x) for x in raw_input().split(' ')]
flag=0
for x in d:
l[x%k]=l[x%k]+1
sum=0
if l[0]!=0:
sum+=1
if (k%2==0):
sum+=1
if k==1:
print 1
elif k==2:
print 2
else:
i=1
j=k-1
while i<j:
sum=sum+(l[i] if l[i]>=l[j] else l[j])
i=i+1
j=j-1
print sum
于 2016-07-13T13:10:48.523 回答