以下是问题https://www.hackerrank.com/challenges/equal的链接
我读了它的社论,无法理解.如果你没有对hackerrank做任何说明,那么肯定你不会看到它的社论,所以这里有一些编辑.
这相当于说,christy可以将一个同事的巧克力带走1,2或5,同时保持其他人的巧克力不受影响.
让我们考虑减少同事的巧克力作为一种手术.为了减少操作次数,我们应该尝试使每个同事的巧克力数量等于组中的最小值(分钟).我们必须通过(A [i] - min)减少第i个人A [i]的巧克力数量.设这个值为x.
This can be done in k operations.
k = x/5 +(x%5)/2 + (x%5)%2
从这里我无法理解
设f(min)是对所有同事进行的操作的总和,以将每个巧克力减少到最小值.但是,有时f(min)可能并不总是给出正确的答案.它也可以是一种情况
f(min) > f(min-1)
f(min) < f(min-5)
因为f(min-5)需要N次操作多于f(min),其中N是同事的数量.因此,如果
A = {min,min-1,min-2,min-3,min-4}
then f(A) <= f(min) < f(min-5)
谁能帮助我理解为什么这有必要检查f(min),f(min-1),...,f(min-4)
考虑这个案子 A = [1,5,5]
正如社论说,这是直观的认为这是最佳的改变A为[1,1,1]与4(2减2)操作,但最好是将其与3改为[0,0,0]( 1减1,2减5)操作.
因此,如果min = minimum element in array,则将所有元素更改为min可能不是最佳的.
您不理解的部分是为了迎合这种情况,我们知道min可能不是最佳,min-x可能更好,但有多大x？那是4点.社论说如果我们知道x最多4个,我们可以简单地蛮力min,min-1...... min-4看看哪个是最小的而不用太多考虑.
x <= 4的推理(不证明!)
如果x> = 5,那么你必须对所有元素使用至少额外的N类型3(减去5)操作,这绝对是不值得的.
基本上它不是操作类型的问题,因为你需要对所有元素使用相同的操作,在你这样做之后,问题不会减少,元素之间的相对差异仍然是相同的,而你的目标是如果相对差异为0,则无需花费N次操作.
换句话说,如果x> = 5,则x-5必须是目标的更佳选择,实际上x%5必须是最佳目标.
(以下是TL; DR部分:版本2)如果您对证明不感兴趣,请跳至上一部分
在编写原始解决方案的过程中,我怀疑x <= 2,我试图在HackerRank上提交一个代码,它只检查最小值f(min-x) where x <= 2,并且它得到了ACed.
我声称,更正式
如果5>(z-min)%5> = 3且(z-min')%5 == 0,则F(min')<F(min)其中min'= min-x,x <= 2, F(k)=元素z变为k的操作的最小数量
(注意表示法,我使用F(),f()在问题中有不同的含义)
这是证明:
如果(z-min)%5 = 1 or 2,那么它至少需要(z-min)/5 + 1操作,而(z-min')%5 == 0 needs (z-min')/5 = (z-min)/5 + 1操作则意味着F(min') = F(min)
如果(z-min)%5 == 3 or 4,那么它至少需要(z-min)/5 + 2操作,而(z-min')%5 == 0 needs (z-min')/5 = (z-min)/5 + 1操作则意味着F(min') < F(min) (or F(min') = F(min)+1)
所以我们证明
如果5>(z-min)%5> = 3且(z-min')%5 == 0,那么F(min')<F(min)其中min'= min-x
现在让我们来证明一下这个范围 x
我们假设(z-min)%5 >= 3 and (z-min')%5 == 0,
所以 (z-min')%5 = (z-min+x)%5 = ((z-min)%5 + x%5)%5 == 0
现在,如果x >= 3,则(z-min)%5永远不能> = 3才能制作((z-min)%5 + x%5)%5 == 0
如果x = 2,那么(z-min)%5可以是3; 如果x = 1,那么(z-min)%5可以是4,以满足两个条件:5> (z-min)%5 >= 3 and (z-min')%5==0
因此我们一起展示
如果5>(z-min)%5> = 3且(z-min')%5 == 0,则F(min')<F(min)其中min'= min-x,x <= 2
注意一个总是可以生成数组P,这样f(min')<f(min),因为你总是可以重复整数,这个方法可以通过这种方法改进,直到输出那些整数不能的数字.这是因为对于无法改进的元素,它们总是需要1个以上的操作
例如:设P = [2,2,2,10] f(min)= 0 + 3 = 3,f(min-2)= 3 + 2 = 5
这里10是可以改进的元素,而2不能,所以我们可以在数组中添加更多10.每2个将使用1个以上的操作min' = min-2,而每个10个将保存1个操作min'.所以我们只需要添加更多10,直到数字(补偿)2的"浪费":
P = [2,2,2,10,10,10,10,10],则f(min)= 0 + 15 = 15,f(min-2)= 3 + 10 = 13
或者只是
P = [2,10,10],f(min)= 6,f(min-2)= 5
(TL的结尾; DR部分!)
EDITED
OMG在HACKERRANK上的测试案例很弱!
故事是我今天早上到办公室的时候,我一直在想这个问题,并且认为我的代码可能存在问题(获得了ACed!)
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int T, n, a[10005], m = 1<<28;
int f(int m){
m = max(0, m);
int cnt = 0;
for(int i=0; i<n;i++){
cnt += (a[i]-m)/5 + (a[i]-m)%5/2 + (a[i]-m)%5%2;
}
return cnt;
}
int main() {
cin >> T;
while(T--){
m = 1<<28;
cin >> n;
for(int i=0; i<n;i++) cin >> a[i], m = min(m,a[i]);
cout << min(min(f(m), f(m-1)),f(m-2)) << endl;
}
return 0;
}你能看到问题吗？
问题是m = max(0, m);!
它确保min-x必须至少为0,但是等等,我上面的证据没有说明范围min-x!它确实可能是消极的!
请记住,原始问题是关于"添加",因此目标没有最大值; 当我们将问题建模为"减去"时,目标也没有最小值(但我将其设置为0!)
使用上面的代码尝试此测试用例:
它强制min-x= 0,所以它给出4作为输出,但答案应该是3
(如果我们使用"添加"模型,目标应为10,a [0]上为+5,a [2],a [0]上为+5,a [1],[1]上为+2, a2])
所以一切都终于正确(我认为...)当我删除线时m = max(0, m);,它允许min-x得到负数并给出3作为正确的输出,当然新代码也得到了ACed ......