Combinatorics Sum

Question

我有一个像{3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8}这样的数组，其中每个整数表示一个百分比。这些数字的目标和应该是100%，但由于它们已经四舍五入到最接近的整数()。5四舍五入)，总数有可能不是100。我需要知道舍入之前的实际值是否可以求和为100%

我试过的:我认为数组中的值可以是四舍五入的结果，在这种情况下，原始值将小于0.5，或者值可以是四舍五入的结果，在这种情况下，原始值将大于0.4。所以我尝试了这个，知道差异(例如从上面的例子)是7，是否存在X*(-0.5) + Y*0.4的组合，其中X和Y是常量，其总和=计算数组的长度，这将给我一个7的差异?这个策略适用于一些测试用例，例如{12,12,12,12,12,12,12}和{13,13,13,13,13,13,13,13,13,13}，但不是这个，根据答案，这个数组可以有100%的目标和，所以我的函数应该返回true。

这是我试过的代码。

Boolean combination(int difference, int count)
{
    decimal d;
    for (int x = 0; x <= count;x++)
    {
        for(int y=0; y<=count-x;y++)
        {
            d = (x * (decimal)(-0.5)) + (y * (decimal)(0.4));
            if ( d == difference)
                return true;
        }
    }
    return false;
}

原始习题，来自topcoder.com SRM 544 DIV 2;成功率<超过700份申请中20%。我猜这是个棘手的问题:)>

在正常的选举中，人们期望每个候选人获得的百分比总和正好是100%。有两种情况可能不会出现这种情况:如果选举存在欺诈，或者报告的百分比是四舍五入的。在最近的一次选举中，选民人数确切地说是10000人。假设选举是公平进行的，每个选民只投票给一个候选人。每位候选人获得的选票百分比在报告前被四舍五入到最接近的整数。位于两个连续整数中间的百分比被四舍五入。选举部正在寻找选举舞弊的证据。你将得到一个int[]百分比，给出每个候选人获得选票的报告百分比。如果选举确实是欺诈性的，则返回一个包含"YES"的字符串，否则返回"NO"(为了清楚起见，请使用引号)。也就是说，如果10000名选民中的每一位都只投票给一名候选人，则返回"YES"，否则返回"NO"。

谢谢你对我的帮助。请不要张贴答案，我所要求的是一个新的思路，我可能没有考虑过。

Answer 1

假设我们有一组整数{ N1, N2, N3 }。

原始数能得到的最小和是多少?

是{ N1-0.5, N2-0.5, N3-0.5 }数组中所有元素的和，可以重写为:

sum({ N1, N2, N3}) - 0.5 * count({ N1, N2, N3 })

最小和必须小于或等于100

原始数能得到的最大和是多少?

是{ N1+0.4999..., N2+0.4999..., N3+0.4999...}数组中所有元素的和，可以重写为:

sum({ N1, N2, N3}) + 0.4999... * count({ N1, N2, N3 })

最大和必须大于或等于100

我们不想处理0.499...，所以我们可以将其重写为:

sum({ N1, N2, N3}) + 0.5 * count({ N1, N2, N3 })

但是在这种情况下，它不能等于 100，也就是说，它必须严格大于100。

因此我们可以在C#中编写以下代码:

static bool CanSumTo100(IList<int> numbers)
{
    return numbers.Sum() - 0.5 * numbers.Count <= 100 &&
           numbers.Sum() + 0.5 * numbers.Count > 100;
}

如果你不想处理浮点数，你可以使用整数:

static bool CanSumTo100(IList<int> numbers)
{
    int sum = numbers.Sum();
    int count = numbers.Count;
    return 2 * sum - count <= 200 &&
           2 * sum + count > 200;
}