a625 - 5. Overhanging Cards

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算要達到給定的凸出長度 c，最少需要多少張卡片。凸出長度由卡片堆疊的每一層的凸出量相加得到，第 i 層卡片凸出量為 1/(i+1) 倍的卡片長度。

解題思路

此題的核心在於計算不同數量卡片堆疊時的總凸出長度，並找到滿足凸出長度大於等於目標值 c 的最小卡片數量。程式碼預先計算了從 1 張到 278 張卡片的總凸出長度，並將結果儲存在 a 陣列中。對於每個輸入的 c 值，程式碼使用迴圈在 a 陣列中尋找第一個大於等於 c 的凸出長度，並輸出對應的卡片數量。這是一種貪心策略，因為它直接尋找滿足條件的最小卡片數量。

複雜度分析

• 時間複雜度: O(N + M)，其中 N 是預計算卡片凸出長度的數量 (278)，M 是輸入的測試案例數量。預計算部分是 O(N)，而對於每個測試案例，搜尋陣列的時間複雜度是 O(N)。
• 空間複雜度: O(N)，用於儲存預計算的卡片凸出長度陣列 a。

程式碼

#include <stdio.h>
int main(){
	float a[278],n=1;
	a[0]=0.5;
	for(int i=1;i<278;i++,n++)
		a[i]=a[i-1]+(1/(n+2));
	float b;
	while(scanf("%f",&b)>0){
		int i;
		for(i=0;a[i]<b;i++){}
		printf("%d card(s)\n",i+1);
	}
}