f442 - 老鷹抓小雞 Eagle
題目描述
題目描述一組數字，以及一個老鷹的初始值和若干次操作。每次操作會嘗試將一個指定的數字替換為老鷹的值，並將老鷹的值更新為被替換的數字。最終輸出替換後的數字陣列。
解題思路
這題的核心是模擬老鷹抓小雞的過程。我們遍歷輸入的數字陣列，然後根據輸入的操作次數進行替換。每次替換時，我們找到陣列中第一個等於目標數字的元素，將其替換為老鷹的值，並更新老鷹的值為被替換的數字。由於題目要求找到第一個匹配的元素，因此我們只需要線性掃描陣列即可。
複雜度分析
- 時間複雜度: O(n*m)，其中 n 是陣列的長度，m 是操作次數。最壞情況下，每次操作都需要遍歷整個陣列才能找到目標數字。
- 空間複雜度: 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 <stdio.h>
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) {
if(x==0)
putchar_unlocked('0');
else{
int stk[6],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
int main(){
int n=read(),e,m,t;
int a[n];
for(int i=0;i<n;++i)
a[i]=read();
e=read();
m=read();
while(m--){
t=read();
for(int i=0;i<n;++i)
if(a[i]==t){
a[i]=e;
e=t;
break;
}
}
for(int i=0;i<n;++i){
write(a[i]);
putchar_unlocked(' ');
}
}