e542 - 11054 - Wine trading in Gergovia
題目描述
題目描述了 Gergovia 城鎮中葡萄酒交易的情形。城鎮由一條街道組成，每個居民都是葡萄酒推銷員。居民可以購買或出售葡萄酒，目標是最小化葡萄酒運輸所需的工作量。工作量與運輸距離成正比，相鄰房屋之間的距離為一單位。輸入給定每個居民的購買或出售數量，要求計算滿足所有居民需求的最小工作量。
解題思路
本題可以使用貪心演算法解決。核心思想是計算前綴和，並對前綴和的絕對值求和。前綴和表示在某個位置累積的葡萄酒數量。前綴和的絕對值表示需要運輸的葡萄酒數量，因為葡萄酒必須從出售者運送到購買者。通過對所有位置的前綴和的絕對值求和，可以得到最小的工作量。
具體步驟如下：
- 初始化一個變數
tmp為 0，用於儲存前綴和。 - 初始化一個變數
ans為 0，用於儲存總工作量。 - 遍歷輸入的每個居民的購買或出售數量
a。 - 將
a加到tmp上，更新前綴和。 - 將
tmp的絕對值加到ans上，更新總工作量。 - 輸出
ans。
複雜度分析
- 時間複雜度: O(n)，其中 n 是居民人數。需要遍歷輸入的 n 個數字。
- 空間複雜度: O(1)，只需要常數級別的額外空間來儲存變數
tmp和ans。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
#include <math.h>
inline int read(){
int a(0),f(1);
char c('0');
while(c>='0'||c=='-'){
if(c=='-'){
f=-1;
c=getchar_unlocked();
}
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a*f;
}
inline void write(long long int x) {
if(x==0)
putchar_unlocked('0');
else{
long long int stk[15],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
int main(){
int n,a;
while(n=read()){
int tmp=0;
long long int ans=0;
while(n--){
a=read();
tmp+=a;
ans+=abs(tmp);
}
write(ans);
putchar_unlocked('\n');
}
}