c782 - PC. 孤單值量測
題目描述
題目要求計算一條馬路上 n 個人之間的孤單值總和。如果第 i 個人和第 j 個人的位置相差大於 k 公尺，則他們會對總孤單值 S 貢獻 w_i * w_j。
解題思路
這題的核心在於有效地計算所有滿足位置差大於 k 的配對 (i, j) 的 w_i * w_j 貢獻。直接使用兩層迴圈計算時間複雜度為 O(n^2)，對於 n <= 2000000 的輸入會超時。
程式碼使用了一個 sliding window 的技巧來優化計算。對於每個位置 i，它找到一個最左邊的位置 s，使得 a[i] - a[s] > k。然後，它知道對於位置 i，只有位置 1 到 s-1 的人與位置 i 的距離大於 k。因此，它只需要計算位置 i 和位置 1 到 s-1 的人的貢獻。
為了加速計算 w_i * w_j 的總和，程式碼使用了 prefix sum 的技巧。w[i] 儲存了 w[1] 到 w[i] 的總和。這樣，計算 w[v[i]] * w[i] 的貢獻時，實際上是在計算 w[1] 到 w[v[i]] 的總和乘以 w[i]。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(n)
程式碼
#pragma GCC optimize(3)
#include <stdio.h>
#define MAX 2000001
#define BUFMAX 1048576
long long sum, w[MAX];
int kase, n, k, length = BUFMAX, a[MAX], v[MAX];
char buf[BUFMAX], tmp, * pt = buf, * end = buf;
inline char freadChar(){
if (pt == end){
if (length < BUFMAX)return EOF;
length = fread(buf, 1, BUFMAX, stdin);
end = buf + length;
pt = buf;
}
return *pt++;
}
inline void freadUInt(int* val){
while ((tmp = freadChar()) < '0')if (tmp == EOF) return;
for(*val = tmp - '0';(tmp = freadChar()) >= '0';* val = (*val << 3) + (*val << 1) + (tmp - '0'));
}
inline void freadLongLong(long long* val){
while ((tmp = freadChar()) < '-')if (tmp == EOF) return;
if (tmp == '-'){
for(*val = freadChar() - '0';(tmp = freadChar()) >= '0';* val = (*val << 3) + (*val << 1) + (tmp - '0'));
*val = -*val;
}
else{
for(*val = tmp - '0';(tmp = freadChar()) >= '0';* val = (*val << 3) + (*val << 1) + (tmp - '0'));
}
}
int main(){
for(scanf(" %d", &kase);kase--;printf("%lld\n", sum)){
sum = 0;
freadUInt(&n), freadUInt(&k);
for (int i = 1; i <= n; )freadUInt(&a[i++]);
for (int i = 1, s = 1; i <= n; ++i){
for(;a[i] - a[s] > k;++s);
v[i] = s - 1;
}
for (int i = 1; i <= n; ++i){
freadLongLong(&w[i]);
sum += w[v[i]] * w[i];
w[i] += w[i - 1];
}
}
}