基础算法题——每日咕咚（规律、数学约分）

短命女 2022-11-21 03:55 164阅读 0赞

#### 每日咕咚 ####

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]  
![题目2][2]  
![题目3][3]

--------------------

#### 题目考察 **找规律**、**数学约分** ####

#### 解题步骤 ####

①、找规律  
每个人排在每个位置的次数是相同的，都是 n-1 的阶乘。  
所以我们只要计算出 每个人在每个位置的超越的时间再乘以 n-1 即可得到全部情况的时间和 sum。将 sum / n-1的阶乘 就是期望时间。  
可得到下面代码

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    ll dp[510];
    
    int main(){ 
    	float n, x, v, sum=0.0;
    // freopen("data.txt", "r", stdin);
    	dp[1]=1;
    	for(int i=2; i<=500; i++)
    		dp[i] = dp[i-1]*i;
    	cin>>n>>x>>v;
    	for(int i=1; i<=n; i++)
    	for(int j=1; j<=n; j++){ 
    		float tmp;
    		cin>>tmp;
    		sum += (dp[n-1]*n*x)/(tmp-v);
    	}
    	printf("%.2f\n", sum/dp[n]);
    	
    	return 0;
    }

这里就有问题了，n<=500的，很明显500的阶乘绝对超限，这里就要运用数学约分。

②、数学约分  
我们能够发现阶乘是能够相互抵消的。  
可得 AC 代码

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    ll dp[510];
    
    int main(){ 
    	float n, x, v, sum=0.0;
    // freopen("data.txt", "r", stdin);
    	dp[1]=1;
    	for(int i=2; i<=500; i++)
    		dp[i] = dp[i-1]*i;
    	cin>>n>>x>>v;
    	for(int i=1; i<=n; i++)
    	for(int j=1; j<=n; j++){ 
    		float tmp;
    		cin>>tmp;
    		sum += x/(tmp-v);
    	}
    	printf("%.2f\n", sum);
    	
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/2659a1eb38a94b7884bfd54b821f7bc3.png
[2]: https://img-blog.csdnimg.cn/20201030012229791.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70#pic_center
[3]: https://img-blog.csdnimg.cn/20201030012248187.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70#pic_center