f707 - 幸運 7 (Lucky Seven)

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出輸入數字中，最接近 7 的倍數的數字。如果有多個數字都符合條件，則輸出最後輸入的那個數字。如果輸入為 0，則結束程式。

解題思路

這題的解題思路是貪婪演算法。我們維護一個變數 ans 來儲存目前找到的最接近 7 的倍數的數字。對於每個輸入數字，我們比較它與 ans 的大小，如果輸入數字更接近 7 的倍數，則更新 ans。判斷是否更接近 7 的倍數的邏輯包含以下幾種情況：

1. 如果 ans 是 7 的倍數，而輸入數字不是 7 的倍數，則輸入數字更接近 7 的倍數。
2. 如果 ans 不是 7 的倍數，而輸入數字是 7 的倍數，則輸入數字更接近 7 的倍數。
3. 如果 ans 和輸入數字都不是 7 的倍數，則比較它們除以 70 的餘數，餘數較小的數字更接近 7 的倍數。
4. 如果 ans 和輸入數字都是 7 的倍數，則比較它們除以 77 的餘數，餘數較大的數字更接近 7 的倍數。

複雜度分析

• 時間複雜度: O(n)，其中 n 是輸入數字的個數。
• 空間複雜度: O(1)，因為我們只使用常數個變數。

程式碼

#include <iostream>
using namespace std;
int ans,input;
bool seven(int x,int y){
	if(x%7==0&&y%7)return 0;
	if(x%7&&y%7==0)return 1;
	if(x%7==0){
		if(x%70<y%70)return 1;
	}
	else{
		if(x%77>y%77)return 1;
	}
	return 0;
}
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	while(cin >> input){
		if(input==0)break;
		if(ans==0)
			ans=input;
		else if(seven(ans,input))
			ans=input;
	}
	cout << ans;
}