g499 - 109北二1.感測器的比較

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在多組感測器 A 和感測器 B 的測量結果中，A 測到低於門檻 (二進位 0) 且 B 測到高於門檻 (二進位 1) 的次數。輸入包含測量次數 n，以及 n 組 A 和 B 的十進位輸出。

解題思路

程式碼遍歷每一組感測器 A 和 B 的輸出。對於每一組，程式碼使用迴圈迭代 32 次，每次檢查 A 和 B 的最低位。如果 A 的最低位是 0 且 B 的最低位是 1，則計數器 ans 增加 1。然後，A 和 B 的值右移 1 位，以便檢查下一位。

複雜度分析

• 時間複雜度: O(n * 32)，其中 n 是測量次數。由於 32 是常數，因此時間複雜度可以簡化為 O(n)。
• 空間複雜度: O(1)，程式碼只使用幾個常數大小的變數。

程式碼

#include <iostream>
using namespace std;
long long x,y,n,ans;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n;
	for(int i=0;i<n;++i){
		cin >> x >> y;
		for(int j=0;j<32;++j){
			if(x%2==0&&y%2){
				++ans;
			}
			x>>=1;
			y>>=1;
		}
	}
	cout << ans;
}