e162 - 01636 - Headshot
題目描述
題目描述了一個俄羅斯輪盤遊戲，給定一個包含 0 和 1 的字串，代表左輪手槍的彈藥配置。0 表示沒有子彈，1 表示有子彈。玩家在朋友開槍後未死亡，現在需要決定是直接開槍還是旋轉槍管後再開槍，以最大化生存機率。
解題思路
解題思路是計算直接開槍和旋轉槍管後開槍的命中概率，並比較它們的大小。
- 直接開槍：計算字串中 '0' 的數量，平方後得到直接開槍不中彈的概率。
- 旋轉槍管：將字串循環移位一次，計算字串中 '0' 的數量乘以字串長度，得到旋轉槍管後不中彈的概率。 比較這兩個概率，如果直接開槍的概率大於旋轉槍管的概率，則輸出 "SHOOT"；如果直接開槍的概率小於旋轉槍管的概率，則輸出 "ROTATE"；如果相等，則輸出 "EQUAL"。
複雜度分析
- 時間複雜度: O(n)，其中 n 是字串的長度。程式碼遍歷字串一次來計算 '0' 的數量。
- 空間複雜度: O(n)，程式碼使用一個大小為 101 的字串陣列
arr來儲存輸入字串。
程式碼
#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>
char arr[101];
int main(){
char a,b=0;
int z=0,zz=0,it=0;
while(a=getchar_unlocked()){
if(a=='0'||a=='1'){
arr[it]=a;
++it;
}
else{
arr[it]=arr[0];
for(int i=0;i<it;++i){
if(arr[i]=='0'){
++z;
if(arr[i+1]=='0')
++zz;
}
}
z*=z;
zz*=it;
if(z>zz)
puts("ROTATE");
else if(z<zz)
puts("SHOOT");
else
puts("EQUAL");
z=0;
zz=0;
it=0;
if(a==-1)b=1;
}
if(b)break;
}
}