Quà kỉ niệm

Điểm: 800 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

TaThanHungbc

Dạng bài

Ngôn ngữ cho phép

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ObjC, OCaml, Pascal, Perl, PHP, Pike, Prolog, PyPy, Python, Racket, Ruby, Rust, Scala, Scheme, ~~Scratch~~, Sed, ~~Swift~~, TCL, Turing, VB, Zig

Mùa hè năm 2024 là mùa hè cuối cùng và nhiều kỉ niệm nhất của CodeTN ở Việt Nam, vì sau đó cậu sẽ đi du học một thời gian khá dài. CodeTN sẽ kết được nhiều bạn mới và có nhiều trải nghiệm hơn ở vùng đất xa quê, đổi lại thì cậu sẽ hiếm khi có cơ hội được gặp mặt với những người bạn thân yêu. Vì vậy, trước khi đi CodeTN sẽ tặng cho những người bạn mình một thùng quà gồm nhiều hộp quà kỉ niệm nhỏ nhằm để các bạn luôn nhớ về cậu ấy.

Ban đầu, số hộp quà trong một thùng quà sẽ khác nhau tùy theo mức độ thân thiết của CodeTN với người bạn đó. Tuy nhiên những người bạn của CodeTN quen biết nhau và có thể sinh lòng đố kị khi người khác nhận được nhiều quà hơn mình. Vì vậy cậu quyết định thêm hoặc bớt số quà trong một số thùng quà để tất cả thùng quà đều có số hộp quà giống nhau. Thật không may là CodeTN đã đóng gói tất cả kiện hàng nên khi muốn thêm hoặc bớt một hộp quà trong một kiện hàng sẽ tốn chi phí nhất định.

Bạn hãy giúp CodeTN tìm chi phí nhỏ nhất để làm cho tất cả thùng quà của cậu ấy có số hộp quà bằng nhau.

$Input$

Dòng đầu tiên chứa số nguyên $n$ là số thùng quà CodeTN đã chuẩn bị.
Dòng tiếp theo chứa $n$ số nguyên, cho biết thùng quà thứ $i$ có $a_{i}$ hộp quà.
Dòng cuối cùng chứa $n$ số nguyên, cho biết chi phí thêm hoặc bớt một hộp quà trong thùng quà thứ $i$ là $t_{i}$ .

$Output$

Gồm một số nguyên duy nhất là chi phí ít nhất để các thùng quà có số hộp quà bằng nhau.

$Sample input$

Copy

4
1 2 3 2
5 2 2 1

$Sample output$

Copy

$Constraint$

$1 \leq n \leq 10^{7}$ .
$1 \leq a_{i} \leq 10^{7}$ .
$1 \leq t_{i} \leq 10^{6}$ .

$Subtask$

Subtask $1$ ( $20 %$ ): $n, a_{i} \leq 100$ .
Subtask $2$ ( $60 %$ ): $n, a_{i} \leq 10^{6}$ .
Subtask $3$ ( $20 %$ ): $n, a_{i} \leq 10^{7}$ .

$Note$

Chi phí để đưa tất cả thùng quà về còn $2$ món quà là: $C = 5 \times (2 - 1) + 2 \times (2 - 2) + 2 \times (3 - 2) + 1 * \times (2 - 2) = 5 \times 1 + 2 \times 0 + 2 \times 1 + 1 \times 0 = 5 + 2 = 7$ .
Có thể chứng minh rằng đây là cách làm tối ưu nhất.

Bình luận

Hãy đọc nội quy trước khi bình luận.

vandung666 đã bình luận 2:54:34 sa, 14/02/2025

include <bits/stdc++.h>

using namespace std; inline int readInt() { int x = 0; int c = getcharunlocked(); while(c < ‘0’ || c > ‘9’) c = getcharunlocked(); while(c >= ‘0’ && c <= ‘9’){ x = x * 10 + (c - ‘0’); c = getcharunlocked(); } return x; } string toString(int128 x) { if(x == 0) return “0”; string s; while(x > 0){ s.pushback(’0’ + (int)(x % 10)); x /= 10; } reverse(s.begin(), s.end()); return s; }

int main(){ int n = readInt();

Copy

vector<int> a(n);
int maxA = 0;
for (int i = 0; i < n; i++){
    a[i] = readInt();
    if(a[i] > maxA) maxA = a[i];
}
vector<int> c(n);
unsigned long long totalW = 0;
for (int i = 0; i < n; i++){
    c[i] = readInt();
    totalW += c[i];
}
unsigned long long half = (totalW + 1ULL) / 2ULL;
vector&lt;unsigned long long> cnt(maxA + 1, 0ULL);
for (int i = 0; i < n; i++){
    cnt[a[i]] += c[i];
}


int median = 0;
unsigned long long prefix = 0;
for (int x = 0; x <= maxA; x++){
    prefix += cnt[x];
    if(prefix >= half) {
        median = x;
        break;
    }
}
__int128 ans = 0;
for (int i = 0; i < n; i++){
    int diff = (a[i] >= median) ? (a[i] - median) : (median - a[i]);
    ans += ( (__int128)c[i] * diff );
}

printf("%s\n", toString(ans).c_str());
return 0;

} ooi voi minh bai nay kha co ban day la code moi nguoi tam khao