題目

有一根粗細均勻長度為 LL 的木棍，先用紅顏色刻度線將它 m 等分，再用藍色刻度線將其 n 等分（m>n），然后按所有刻度線將該木棍鋸成小段，計算并輸出長度最長的木棍的長度和棍數。

輸入

輸入僅有一行，包含三個正整數 L，m 和 n，兩兩之間用一個空格分隔。（1≤L≤100000）

輸出

輸出包含兩個正整數 a 和 k，分別表示最長木棍的長度和根數。(為了簡化題目的難度，所有的測試數據中 m 和 n 一定是 L 的約數）。兩數之間用一個空格分隔

輸入樣例

12 6 4

輸出樣例

2 4

思路：

開兩個桶，一個記錄所有的切割點，一個記錄長度

首先對木棍 l 進行切割，將兩次切割的切割點存入第一個桶中

然后對枚舉第一個桶，如果某點被切割，就記錄切割長度存入第二個桶中

最后枚舉第二個桶，尋找最長的長度并輸出相應個數

源程序

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 100000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std; bool bucket[N]; int len[N]; int main(){int l,m,n;scanf("%d%d%d",&l,&m,&n);int num=l/m;for(int i=0;i*num<=l;i++)bucket[i*num]=true;num=l/n;for(int i=0;i*num<=l;i++)bucket[i*num]=true;int i=0;for(int j=1;j<=l;j++){if(bucket[j]){len[j-i]++;i=j;}}int res=0;for(int i=1;i<=l;i++)if(len[i]>0)res=i;printf("%d %d",res,len[res]);return 0; }

總結

以上是生活随笔為你收集整理的锯木棍（51Nod-2143）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。