f290 - 德潤的大軍
題目描述
題目描述了德潤大帝的士兵排列問題。給定 N 個士兵的防禦力，士兵的攻擊力根據其位置決定：頭尾士兵的攻擊力等於其防禦力，中間士兵的攻擊力等於其左右鄰居防禦力的總和。目標是計算所有士兵的攻擊力，並按照攻擊力從小到大排序，如果攻擊力相同，則按照防禦力從小到大排序，最後輸出每個士兵的攻擊力和防禦力。
解題思路
解題思路如下：
- 讀取士兵的防禦力。
- 計算每個士兵的攻擊力。頭尾士兵的攻擊力等於其防禦力，中間士兵的攻擊力等於其左右鄰居防禦力的總和。
- 將每個士兵的攻擊力和防禦力儲存在一個結構體中。
- 使用
sort函數按照攻擊力從小到大排序，如果攻擊力相同，則按照防禦力從小到大排序。 - 輸出排序後的每個士兵的攻擊力和防禦力。
複雜度分析
- 時間複雜度: O(N log N)
- 空間複雜度: O(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 <iostream>
#include <algorithm>
using namespace std;
struct p{
int atk,def;
};
inline bool cmp(p x,p y){
if(x.atk<y.atk||(x.atk==y.atk&&x.def<y.def))return 1;
return 0;
}
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n=read();
p a[n];
for(int i=0;i<n;++i){
a[i].def=read();
}
a[0].atk=a[0].def;
a[n-1].atk=a[n-1].def;
for(int i=1;i<n-1;++i){
a[i].atk=a[i-1].def+a[i+1].def;
}
sort(a,a+n,cmp);
for(int i=0;i<n;++i){
write(a[i].atk);
putchar_unlocked(' ');
write(a[i].def);
putchar_unlocked('\n');
}
}