d479 - 星级青蛙

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算當有 X 隻青蛙時，所有青蛙跳到對方飛行器所需的最小步數。青蛙每次可以向前跳一步，或跳到前面青蛙的前面一格（如果該格沒有青蛙）。

解題思路

題目描述的跳躍方式實際上可以簡化為一個數學公式。假設有 X 隻青蛙，它們需要交換位置。可以觀察到，每隻青蛙需要跳 X 步才能到達對方的飛行器。由於有 X 隻青蛙，總步數是 X * X。此外，每隻青蛙在跳躍過程中，會佔據一個位置，因此需要加上 X 步來調整位置。所以，總步數是 X * X + X，也可以寫成 X * (X + 1) 或 (X << 1) + X * X。程式碼直接計算這個公式的結果。

複雜度分析

• 時間複雜度: O(1)
• 空間複雜度: O(1)

程式碼

#include <stdio.h>
int main(){
	int a;
	while(scanf("%d",&a)>0)
		printf("%d\n",(a<<1)+a*a);
}