f461 - 現金兌換點卷
題目描述
題目描述了奧利佛有 N 張卡片，每張卡片上都有一個數字。奧利佛可以通過計算任意兩張卡片數字的差的絕對值來獲得現金點數。目標是計算奧利佛可以獲得的最大現金點數總和。
解題思路
本題的核心思想是將卡片上的數字進行排序，然後將最大的數字和最小的數字配對，次大的數字和次小的數字配對，以此類推。這樣可以最大化每對卡片之間的差值，從而最大化總現金點數。
具體步驟如下：
- 讀取卡片數量 N 和每個卡片上的數字 a。
- 對卡片上的數字進行排序。
- 計算總現金點數：對於前 N/2 個數字，將第 i 個最大的數字和第 i 個最小的數字配對，計算差的絕對值，並將其加到總和中。
- 如果 N 是偶數，則需要減去中間的差值，因為中間的差值被重複計算了。
- 輸出總現金點數。
複雜度分析
- 時間複雜度: O(n log n) 排序操作佔據主導地位，時間複雜度為 O(n log n)。其餘操作，如讀取輸入、計算總和等，時間複雜度為 O(n)，因此總時間複雜度為 O(n log n)。
- 空間複雜度: O(n) 需要一個大小為 n 的數組來存儲卡片上的數字。
程式碼
#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 <algorithm>
long long int a[100001],n;
inline long long int read(){
long long 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[32],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
int main(){
while(scanf("%lld",&n)>0){
getchar_unlocked();
for(int i=0;i<n;++i)a[i]=read();
long long int ans=0,nn=(n>>1),sum=0;
std::sort(a,a+n);
for(int i=0,r=n-i-1;i<nn;++i,--r){
sum+=a[r]-a[i];
ans+=sum;
}
ans*=2;
if(n%2==0)ans-=sum;
write(ans);
putchar_unlocked('\n');
}
}