日期:2025年1月21日
作者:王一哲
ZeroJudge 題目連結
有
若一個人位在
第一行輸入兩個數字
子題配分
輸出安排這兩場會議,使得參與會議的人移動距離總和最小值為何。
6 2
5 2 0 6 9 6
2
7 3
6 3 2 2 0 9 8
4
本題的說明似乎不太清楚,看起來開會的地點應該是在某個人所在的位置,所以題目中的
若中位數
如果用滑動視窗解題,固定視窗範圍為
費時最久約為 0.9 s,使用記憶體最多約為 40 MB,通過測試。
from collections import deque
n, k = map(int, input().split()) # 共有 n 個人,每場會議要有 k 個人
x = sorted(list(map(int, input().split()))) # 每個人的位置,由小到大排序
m = k//2 # k 的一半
curr = -sum(x[:m]) + sum(x[m:k]) # 編號 0 ~ k-1 的人移動的距離總和
if k%2 == 1: curr -= x[m] # 如果 k 是奇數,第4行會多加上 x[m],要扣掉
dp = [curr] # 以編號 k-1 ~ n-1 的人所在位置當作開會的位置,同組 k 個人移動的距離總和
minleft = ans = float('INF') # 第1組的最小值,答案
rhs = deque() # 第2組的最小值,可能會從左端出界
for left in range(n-k): # 依序取出界的左端點 left = 0 ~ n-k,找各種分組的距離,滑動視窗,寬度固定為 k
curr = curr + x[left] - x[left+m] - x[left+k-m] + x[left+k] # 更新視窗內的移動總距離
dp.append(curr) # dp 加上新的移動總距離
if left >= k-1: # 開始可以取第2組
minleft = min(minleft, dp[left-k+1]) # 更新 minleft
if left >= k: rhs.popleft() # 移除第2組左端出界的值
while rhs and curr <= rhs[-1]: rhs.pop() # 如果 rhs 還有資料而且 curr 小於等於 rhs 最後面的值,移除最後一項
rhs.append(curr) # curr 加入 rhs,最後一項一定是第2組的最小值
ans = min(ans, minleft + rhs[-1]) # 更新 ans
print(ans)
費時最久約為 72 ms,使用記憶體最多約為 5.4 MB,通過測試。
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <climits>
typedef long long LL;
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, k; cin >> n >> k; // 共有 n 個人,每場會議要有 k 個人
vector<LL> x (n); // 每個人的位置,輸入之後由小到大排序
for(int i=0; i<n; i++) cin >> x[i];
sort(x.begin(), x.end());
int m = k/2; // k 的一半
LL curr = 0; // 範圍內的人移動的距離總和
for(int i=0; i<m; i++) curr -= x[i]; // 編號 0 ~ k-1 的人移動的距離總和
for(int i=m; i<k; i++) curr += x[i];
if (k%2 == 1) curr -= x[m]; // 如果 k 是奇數,第4行會多加上 x[m],要扣掉
vector<LL> dp = {curr}; // 以編號 k-1 ~ n-1 的人所在位置當作開會的位置,同組 k 個人移動的距離總和
LL minleft = LLONG_MAX, ans = LLONG_MAX; // 第1組的最小值,答案
deque<LL> rhs; // 第2組的最小值,可能會從左端出界
for(int left=0; left<n-k; left++) { // 依序取出界的左端點 left = 0 ~ n-k,找各種分組的距離,滑動視窗,寬度固定為 k
curr = curr + x[left] - x[left+m] - x[left+k-m] + x[left+k]; // 更新視窗內的移動總距離
dp.push_back(curr); // dp 加上新的移動總距離
if (left >= k-1) { // 開始可以取第2組
minleft = min(minleft, dp[left-k+1]); // 更新 minleft
if (left >= k) rhs.pop_front(); // 移除第2組左端出界的值
while(!rhs.empty() && curr <= rhs.back()) rhs.pop_back(); // 如果 rhs 還有資料而且 curr 小於等於 rhs 最後面的值,移除最後一項
rhs.push_back(curr); // curr 加入 rhs,最後一項一定是第2組的最小值
ans = min(ans, minleft + rhs.back()); // 更新 ans
}
}
cout << ans << "\n";
return 0;
}
APCS
、Python
、C++