問題：1561. 買木頭

類型：省賽、數(shù)組問題、二分答案、貪心、2015江蘇省青少年信息學(xué)奧林匹克競賽復(fù)賽

---

題目描述：

有 n 個木材供應(yīng)商，每個供貨商有長度相同一定數(shù)量的木頭。長木頭可以鋸短，但短木頭不能接長。有一個客人要求 m 根長度相同的木頭。要求計算出，此時供貨商提供的木頭滿足客人要求的最長的長度是多少。
例如 n=2,m=30，兩個供貨商的木頭為
12,10 第 1 個供貨商的木頭長度為 12 ，共有 10 根；
5,10 第 2 個供貨商的木頭長度為 5 ，共有 10 根。
計算的結(jié)果為 5 ，即長度為 12 的木頭一根可鋸出兩根長度為 5 的木頭，多余的無用，長度為 5 的木頭不動，此時可得到 30 根長度為 5 的木頭。

輸入：

整數(shù) n,m,L1?,S1? （1≤n≤10000,1≤m≤1000000,1≤L1?≤10000,1≤S1?≤100）
其中 L1? 是第一個供貨商木頭的長，S1? 是第一個供貨商木頭數(shù)量。其他供貨商木頭的長度和數(shù)量 Li? 和 Si?（i≥2），由下面的公式給出：
Li?=((Li?1×37011+10193)mod10000)+1
Si?=((Si?1×73011+24793)mod100)+1

輸出：

一個整數(shù)，即滿足要求的 m 根長度相同的木頭的最大長度。

樣例：

輸入：

10 10000 8 20

輸出：

201

---

完整代碼如下：

#include<bits/stdc++.h> 
using namespace std;int m,cmax=0;
vector<int> v;bool cmp(int a,int b){return a>b;
}int findNum(int mid){int c=0,t;for(int i=0;i<v.size();i++){t=v[i];while(t>=mid){++c;t-=mid;}	}return c;
}void myFind(int l,int r){if(l>r){return;}int mid;mid=l+r>>1;if(m>findNum(mid)){return myFind(l,mid-1);}else{cmax=mid;return myFind(mid+1,r);}}
int main(){//一、分析問題//已知：有n個木材供應(yīng)商。需要m 根長度相同的木頭。L 是第一個供貨商木頭的長，S是第一個供貨商木頭數(shù)量。 //未知：供貨商提供的木頭滿足客人要求的最長的長度是多少。//關(guān)系：長木頭可以鋸短，但短木頭不能接長。其他供貨商木頭的長度和數(shù)量 Li 和 Si（i≥2），由下面的公式給出：//Li=((Li-1×37011+10193)mod10000)+1//Si=((Si-1×73011+24793)mod100)+1//二、數(shù)據(jù)定義 int n,li,si;//三、數(shù)據(jù)輸入cin>>n>>m>>li>>si; for(int i=0;i<n;i++){for(int j=0;j<si;j++){v.push_back(li);} li=(li*37011+10193)%10000+1;si=(si*73011+24793)%100+1;}//四、數(shù)據(jù)計算 sort(v.begin(),v.end(),cmp);myFind(1,v[0]);//五、輸出結(jié)果 cout<<cmax;return 0;	
}