问题：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;
}
