j180 - 戰備存糧 (Food)

🔗 前往 ZeroJudge 原題

題目描述

題目描述了某個國家為了戰爭儲備食物，初始有 n * m 份食物。每天會吃掉盡可能多的食物，每次吃掉的數量是總食物數除以 m 的整數部分，如果剩餘的食物大於 0，則再吃掉 1 份。求需要多少天才能吃完所有的食物。

解題思路

這道題可以使用貪心策略來解決。每次都盡可能多地吃掉食物，直到食物數量為 0。程式碼中，sum 變數表示剩餘的食物數量，ans 變數表示天數。在迴圈中，每次從 sum 中減去 sum / m (可以吃的數量) 加上 sum % m ? 1 : 0 (如果剩餘數量大於 0，則再減 1)。迴圈持續到 sum 為 0，此時 ans 就是答案。

複雜度分析

• 時間複雜度: O(nm) (n 是初始食物總量，m 是每天吃的比例。最壞情況下，每次只吃掉 1 份食物，需要 nm 天)
• 空間複雜度: O(1) (只使用了常數個變數)

程式碼

#include <iostream>
using namespace std;
int n,m;
int main(){
	while(cin >> n){
		if(n==-1)return 0;
		cin >> m;
		int sum=n*m,ans=0;
		while(sum){
			sum-=sum/m+(sum%m?1:0);
			++ans;
		}
		cout << ans << "\n";
	}
}