CSES - Stick Lengths | Độ dài que
Xem PDF
Điểm:
1100 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Có \(n\) que với một số độ dài. Nhiệm vụ của bạn là sửa đổi các que sao cho mỗi que có cùng chiều dài.
Bạn có thể kéo dài và rút ngắn từng thanh. Cả hai thao tác đều có chi phí \(x\) trong đó \(x\) là chênh lệch giữa độ dài mới và độ dài ban đầu.
Tổng chi phí tối thiểu là bao nhiêu?
Input
- Dòng đầu vào đầu tiên chứa một số nguyên \(n\): số lượng que.
- Sau đó, có \(n\) số nguyên: \(p_1,p_2,\ldots,p_n\): độ dài của que.
Output
- In một số nguyên: tổng chi phí tối thiểu.
Constraints
- \(1 \le n \le 2 \cdot 10^5\)
- \(1 \le p_i \le 10^9\)
Example
Sample input
5
2 3 1 5 2
Sample output
5
Bình luận
cho mình hỏi sao mình cnp kết quả bài này ko được thế
code
-
tantaidepzai
•
8:25 p.m. 7 Tháng 3, 2025
•
0
Phản hồi
Chia sẻ
3 bình luận nữaCode bạn thì đúng nhưng chạy chậm và không tối ưu với các số lớn hơn nên WA một số test
*- Code tham khảo --"thêm dấu # vào nha":
include <bits/stdc++.h>
using namespace std;
const long long INF=1e18;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
cin>>n;
vector<int> a(n);
for (auto&x:a) cin>>x;
sort(a.begin(), a.end());
long long mid=a[n/2];
long long ans=0;
for (auto &x:a){
ans+=abs(x-mid);
}
cout<<ans;
return 0;
}