我的算法中的缺陷在哪里,无法找到每对总和不除以 K 的最大子集?



我留下了关于我的逻辑是什么的评论。它的工作方式应该是,例如,如果我们有K=3S={1,7,2,4},那么每对的和不除以K的最大子集是{1,7,4}

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
    static void Main(String[] args)
    {
        int k = Int32.Parse(Console.ReadLine().Split(' ')[1]);
        var S = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
        // first get all pairs in S whose sum doesn't divide k, 
        // each pair in their own subset set of S
        var subsets = from i in S
                      from j in S
                      where i < j && ((i + j) % k != 0)
                      select new HashSet<int>() { i, j };
        // for each subset, for each number in the original set 
        // not already in the subset, if the number summed with
        // every numer in the subset doesn't divide k, add the
        // number to the subset
        foreach(var ss in subsets)
             foreach(int n in S.Where(q => !ss.Contains(q)))
                if(ss.All(m => (m + n) % k != 0))
                   ss.Add(n);
        // get the size of the largest subset, print to console
        int max = subsets.Select(ss => ss.Count).Max();
        Console.WriteLine(max);
    }
}

您对问题的算法可能是错误的,但意外的行为是由于代码中的错误造成的。(但即使你修复了它,我认为它对在线法官来说太慢了,而且你可能会错过一些棘手的案件,你可以尝试提交它)。

HashSet对象subsets不会更新,因为当您调用Add时,整数会添加到另一个HashSet的副本中。

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

public class Test
{
    public static void Main(String[] args)
    {
        ...
       foreach(var ss in cnt){
             foreach(int n in S.Where(q => !ss.Contains(q)))
                if(ss.All(m => (m + n) % k != 0)){
                   ss.Add(n);
                }
          // Log here, you will see the size is updated to 3
            Console.WriteLine(ss.Count);
        }
        // Log here, it is still printing 2 !         
        foreach(var ss in cnt)
             Console.WriteLine(ss.Count);
        // get the size of the largest subset, print to console
        int max = ...
        Console.WriteLine(max);
    }
}

一个简单的修复方法是首先新建一个全局哈希集列表,并更新该列表

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

public class Test
{
    public static void Main(String[] args)
    {
        int k = Int32.Parse(Console.ReadLine().Split(' ')[1]);
        var S = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
        List<HashSet<int>> cnt = new List<HashSet<int>>();
        // first get all pairs in S whose sum doesn't divide k, 
        // each pair in their own subset set of S
        cnt = (from i in S
                      from j in S
                      where i < j && ((i + j) % k != 0)
                      select new HashSet<int>() { i, j }).ToList();
        // for each subset, for each number in the original set 
        // not already in the subset, if the number summed with
        // every numer in the subset doesn't divide k, add the
        // number to the subset
        foreach(var ss in cnt){
             foreach(int n in S.Where(q => !ss.Contains(q)))
                if(ss.All(m => (m + n) % k != 0)){
                   ss.Add(n);
                }
        }
        // get the size of the largest subset, print to console
        int max = cnt.Max(ss => ss.Count);
        Console.WriteLine(max);
    }
}

然而,这个问题在O(k)(如果不计算I/O时间,即O(N))中可以很容易地解决

这是我在C++中接受的代码

#include<bits/stdc++.h>
using namespace std;
int n,k,a,c[105] = {0},ans=0;
int main() {
    cin >> n >> k;
    for(int i=0; i<n;i++) cin >> a, c[a%k]++;
    for(int i=1; i<=k/2; i++){
        if(k%2 == 0 && i==k/2 && c[i]) ans++;
        else ans += max(c[i], c[k-i]);
    }
    if(c[0] && ans) ans++;
    if(!ans) ans++;
    cout << ans << endl;
    return 0;
}

这背后的概念是模块化算法:

(a+b)%k = 0 is equavalent to (a%k + b%k)%k = 0

所以实际上,我们只计算模k等于0,1,2…k-1的元素数量,将它们存储在c[0], c[1]...c[k-1]

那么逻辑上对于c[1]&c[k-1]不能一起选择,所以我们选择计数较大的一个。类似地,c[2] & c[k-2]不能一起选择,等等。

不过也有一些特殊情况,您可以看到我的代码并查看它。

注意这个问题的一个更棘手的地方是(我认为这是一个糟糕的问题语句),如果结果集大小为1,那么它总是一个有效集,即使唯一的元素可以被k整除。(即,ans永远不会是0)

在第二个循环中,当您编写ss.Add(n);时您将'n'添加到哈希集ss的副本中。

因此在foreach部分之后,subsets与之前的集合保持在一起。

您可以手动计算foreach内部的最大值作为快速解决方案

使用您的方法,您将计算出所有数字都满足条件的子集,但您不会将数字的子集添加到您的整体subsets中。因此,当你在寻找最大的子集时,你不会找到正确的子集。

    foreach(var ss in subsets)
    {
         foreach(int n in S.Where(q => !ss.Contains(q)))
         {
            if(ss.All(m => (m + n) % k != 0))
               ss.Add(n);
         }
     //Add the subset ss to subsets or replace it
    }

最新更新