问题：1413. 切割绳子

类型：贪心，二分，noip2017普及组初赛

---

题目描述：

有 n 条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出 m 条长度相同的绳段，求绳段的最大长度是多少。

输入：

第一行是一个不超过 100 的正整数 n 。

第二行是 n 个不超过 10^6 的正整数，表示每条绳子的长度。

第三行是一个不超过 10^8的正整数 m 。

输出：

绳段的最大长度，若无法切割，输出Failed。

样例：

输入：

3
5 10 8
2

输出：

8

---

完整代码如下：

#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 条绳子,每条绳子的长度已知且均为正整数。
	//未知：切割出 m 条长度相同的绳段，求绳段的最大长度是多少。
	//关系：绳子可以以任意正整数长度切割，但不可以连接。贪心 

	
	//二、数据定义 
	int n,t;

	//三、数据输入
	cin>>n; 
	for(int i=0;i<n;i++){
		cin>>t;
		v.push_back(t);
	}
	cin>>m;
	//四、数据计算 
	sort(v.begin(),v.end(),cmp);
	myFind(1,v[0]);
	

	//五、输出结果 
	if(0!=cmax){
		cout<<cmax;
	}else{
		cout<<"Failed";
	}
	return 0;	
}