SPOJ「abs（a-b）I」錯誤答案issue

這是我對問題陳述的方法http://www.spoj.com/problems/ABSP1/ - 請檢查我的代碼是否存在任何轉角情況，因爲根據我的測試用例，它會給出正確的答案。SPOJ「abs（a-b）I」錯誤答案issue

問題陳述：

您給出N個數的非遞減的順序數組。您有可以回答給定數組中所有不同對的絕對差的總和。

scanf（「％d」，& TotalElements）;

for(i=0;i<TotalElements;i++) 
     scanf("%d",&Array[i]); 

    FirstSum=TotalSum=0;   
    for(i=0;i<TotalElements;i++) 
     FirstSum+=abs(Array[i]-Array[0]); 

    TotalSum=FirstSum; 
    SumTillNow=Array[0]; 
    for(i=1;i<TotalElements;i++){ 

     Difference=Array[i]-Array[0]; 
     NextSum=FirstSum-Difference*(TotalElements-i)-SumTillNow+(i)*Array[0];   
     TotalSum+=NextSum; 
     SumTillNow+=Array[i]; 

    } 

    printf("%lld\n",TotalSum);

來源

2014-06-05 user3166642

你可以簡單介紹一下你的代碼以及問題陳述嗎？ –

問題設定者似乎沒有足夠的經驗。這是爲什麼：

他說不同的對，但它似乎並不像它。也許他想說的是UNORDERED對。
測試數據不符合約束條件。聲明輸入數據驗證這一點。使用64位有符號整數進行輸入。

請記住這兩點（尤其是第2點），並且應該被接受。

來源

2014-06-06 07:54:59 shebang

這是一個答案或評論？對於評論，你可以在問題 –

@PhamTrung下添加一個答案。 – shebang

想到一件事。 SPOJ說：

Do you know what distinct pair means? Suppose you have an array of 3 elements: 3 5 6 
Then all the distinct pairs are: 
3 5 
3 6 
5 6

如果改爲有3個元素的數組：3 3 4那麼有多少不同對你有嗎？同樣的：3 3 3. SPOJ並不完全說明不同的對是什麼，但我假設兩對a1 a2和b1 b2僅在a1 <> a2或b1 <> b2時不同。如果是這種情況，那麼你需要過濾掉數組中的所有重複項。

來源

2014-06-05 03:54:44 Penguino

這並不重要，因爲非明顯的對之間的差異爲0 –

@PhamTrung它的確如此。 1 2的答案是1但是1 2 2是2 – shebang

@shebang以哪種方式？你的例子清楚地表明我們不應該過濾出重複。 –

根據我你的邏輯是好的。 我認爲錯誤的答案可能與您使用的變量類型有關。

讓我們仔細看看代碼中的這條語句。

NextSum=FirstSum-Difference*(TotalElements-i)-SumTillNow+(i)*Array[0]; 

Here FirstSum = summation(A[k] - A[0]) for all k > 0 
       = summation(A[k]) - N*A[0] 

Difference = A[i] - A[0].

因此，語句變成：

NextSum = summation(A[k]) - N*A[0] - (A[i] - A[0])*(N-i) - summation(A[j]){j<i} + i*A[0] 
     = summation(A[m]){m >= i} - A[i]*(N-i)

這筆款項考慮到A[i]和A[m]其中m > i之間所有的絕對差值。這應該給你正確的答案。

此外，還有一個更簡單的方法來進行求和。爲了完整性，我將其包括在內。

如果看一下的次數各A [i]於將出現在絕對差之和，

「-A [0]」將出現N-1次
「-A [1 ]「將出現N-2次，A [1]將出現1次。因此淨效應將是(1 - (N-2))*A[1]。

類似地，第[i]項應爲(i - (N-i-1))*A[i] = (2i + 1 - N)*A[i]。

您可以相應地計算出系列。

來源

2014-06-05 06:20:34

我得到它接受使用相同的邏輯，但只是將int更改爲長long int – user3166642

SPOJ「abs（a-b）I」錯誤答案issue

回答

相關問題