k468 - 打靶 (Target)
題目描述
題目描述一個打靶的遊戲，有 n 個靶子，每個靶子有其分數 a[i]。玩家每次射擊一個靶子，如果該靶子的射擊次數達到 s 次，且該靶子的分數等於目標分數 f，則遊戲結束。目標是找出遊戲結束時射擊的靶子總數。如果沒有射擊到目標靶子達到 s 次，則不輸出任何東西。
解題思路
這題可以使用貪心策略來解決。我們遍歷每個靶子，如果該靶子的射擊次數小於其大小，或者已經射擊過該靶子且上次射擊的位置小於當前位置，則射擊該靶子，並增加射擊次數。如果射擊的靶子分數等於目標分數 f，且射擊次數達到 s，則輸出射擊次數並結束程式。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(n)
程式碼
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,s,f,a[3505],ct[10005],ans;
vector <ll> b[10005];
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n >> s >> f;
for(int i=0;i<n;++i){
cin >> a[i];
b[a[i]].push_back(i);
}
for(int i=0;i<n;++i){
if(ct[a[i]]>=b[a[i]].size()||(ct[a[i]]&&b[a[i]][ct[a[i]]-1]>=i))continue;
ct[a[i]]+=2;
++ans;
if(a[i]==f&&ct[a[i]]>=s){
cout << ans;
return 0;
}
}
}