最小值的最大化问题！！！二分搞定……
代码如下：
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<iomanip> 5 #include<cmath> 6 #include<cstring> 7 #include<vector> 8 #define ll __int64 9 #define pi acos(-1.0) 10 #define MAX 50000 11 using namespace std; 12 int an[100005]; 13 int main(){ 14 int n,m,i,sum,left,right=0,mid,t; 15 while(cin>>right>>n>>m){ 16 an[0] = 0; 17 an[n+1] = right; 18 for (i=1;i<=n;i++) 19 cin>>an[i]; 20 sort(an,an+n+1); 21 left = 0; 22 for (i=0;i<=n;i++){ 23 an[i] = an[i+1]-an[i]; 24 if (left > an[i]) left = an[i]; 25 } 26 while (left<=right){ 27 mid = (left+right)/2; 28 sum = 0;t = 0; 29 for (i=0;i<n;i++){ 30 if (sum+an[i]<mid){ 31 sum += an[i]; 32 t++; 33 } 34 else { 35 sum = 0; 36 } 37 } 38 if (t>m){//t>m,说明m取大了 39 right = mid-1; 40 } 41 else{ 42 left = mid+1; 43 } 44 } 45 cout<<right<<endl; 46 } 47 return 0; 48 }