f447 - 12918 - Lucky Thief
題目描述
題目描述了小偷找到 n 把鑰匙和 m 間房子，他需要找出每把鑰匙對應的房子。題目要求計算小偷至少需要嘗試多少次才能確定所有鑰匙和房子的配對。
解題思路
題目實際上要求的是在最壞情況下，需要嘗試多少次才能確定所有鑰匙對應的房子。由於每把鑰匙只能打開一扇門，我們可以考慮貪心策略。 假設小偷已經嘗試了 k 次，並且每次嘗試都失敗了。那麼，小偷已經排除了 k 個錯誤的配對。 如果 n = m，那麼最壞情況下，需要嘗試 n-1 次才能確定所有配對。 如果 n < m，那麼小偷只需要嘗試 n 次就能確定 n 個鑰匙對應的房子。 題目給定的公式 (b-a)*a+(a-1)*a/2 實際上是計算在嘗試 a 次後，最壞情況下需要嘗試的次數。 公式可以理解為：
- (b-a)*a: 嘗試 a 次後，還剩下 b-a 個未匹配的鑰匙，每個鑰匙需要嘗試 a 次才能確定是否匹配。
- (a-1)*a/2: 嘗試 a 次後，已經匹配了 a 個鑰匙，這 a 個鑰匙之間存在 (a-1)*a/2 個可能的錯誤配對。
複雜度分析
- 時間複雜度: O(1)
- 空間複雜度: O(1)
程式碼
#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[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
int main(){
int t,a,b;
t=read();
while(t--){
a=read();
b=read();
write((b-a)*a+(a-1)*a/2);
putchar_unlocked('\n');
}
}