链接：

 

题意：

输入n条线段，把每条线段变成原线段的一条子线段，使得改变之后所有线段等长且不相交（端点可以重合）。

输出最大长度（用分数表示）。

 

分析：

二分线段的长度，然后用贪心法检验可行性，最后把小数转换为分数。

这样做虽然能AC，但这也是测试数据的问题。原因是贪心的方法不完全正确。

无论是按线段的左端点排序，还是按右端点排序，都能找到出错的例子（见下面的测试数据）。

目前网上几乎所有关于这道题的题解都有这个问题，所以这道题还没解决。。。

 

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 struct TYPE { 7     int f, b; 8     bool operator < (const TYPE& that) const { 9         return b < that.b;10     }11 } a[100000+5];12 13 int main(){14     int n;15     while(~scanf("%d", &n)){16         for(int i = 0; i < n; i++) scanf("%d%d", &a[i].f, &a[i].b);17         sort(a, a + n);18 19         double L = 0, R = 1000000; //二分法20         while(R - L > 1e-9){21             int i;22             double M = L + (R - L) / 2, pos = 0;23             for(i = 0; i < n; i++){ //贪心法24                 if(pos < a[i].f) pos = a[i].f;25                 if(pos + M > a[i].b) break;26                 pos += M;27             }28             if(i == n) L = M;29             else R = M;30         }31 32         int ac = 0, ad = 1; //小数转分数33         for(int d = 1; d <= n; d++){34             int c = round(L * d);35             if(fabs(1.0*ac/ad - L) > fabs(1.0*c/d - L)) ac = c, ad = d;36         }37         printf("%d/%d\n", ac, ad);38     }39     return 0;40 }
       
      
     

 

测试数据：

input1:

2

0 7

3 6

output1:

3/1

 

input2:

2

1 6

2 4

output2:

2/1