Zamiana elementów w tablicach tak aby ich sumy były równe
Ostatnio zmodyfikowano 2017-07-14 13:58
Mateusz99 Temat założony przez niniejszego użytkownika |
Zamiana elementów w tablicach tak aby ich sumy były równe » 2017-07-14 12:41:20 Próbuje rozgryźć algorytm, który sprawdza czy da się podmieniać elementy w dwóch tablicach tak aby ich suma była równa, jednak spotykam się z kilkoma problemami. const long m = 1000000;
for( int i = 0; i < n; i++ )
{
sumaA += A[ i ];
sumaB += B[ i ];
}
bool wynik = false;
long d = sumaB - sumaA;
if( d % 2 == 0 )
{
d /= 2;
for( int i = 0; i < n; i++ )
zlicz[ A[ i ] ] ++;
for( int i = 0; i < n; i++ )
if( 0 < = B[ i ] - d && B[ i ] - d <= m && zlicz[ B[ i ] - d ] > 0 )
wynik = true;
}
Nie za bardzo rozumiem jaki jest cel dzielenia sumy przez 2 oraz czemu gdy suma jest nieparzysta od razu wiadomo, że nie da się zamienić elementów tak aby sumy były równe, druga sprawa to warunki w ostatnim if'ie. |
|
RazzorFlame |
» 2017-07-14 13:41:05 Jeśli różnica dwóch sum nie jest parzysta to nie ma opcji, żeby podzielić po równo takie sumy. Któraś będzie musiała być większa a któraś mniejsza.
Przykład:
SumaA = 40;
SumaB = 30;
Okej, różnica jest parzysta (40-30 = 10), można zmienić ich wartość na:
SumaA = 35;
SumaB = 35;
Drugi przykład:
SumaA = 41;
SumaB = 30;
Różnica nie jest parzysta (41-30 = 11), najbliższa zbliżona do siebie ich wartość to:
SumaA = 36;
SumaB = 35; |
|
Mateusz99 Temat założony przez niniejszego użytkownika |
» 2017-07-14 13:58:20 No tak >,< faktycznie racja :) |
|
| « 1 » |