首页 > 代码库 > sdut 2846 Remove Trees (二分 + 贪心)

sdut 2846 Remove Trees (二分 + 贪心)

题目

和poj 上的一道题几乎一样。

题意:已知n棵树距第一棵树的距离,求删掉m棵树后的 树之间 的最小距离  的最大值。

思路:二分枚举最小的距离,注意二分的写法。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 #include <cmath>
 6 #include <algorithm>
 7 using namespace std;
 8 const int maxn = 50000+10;
 9 int a[maxn];
10 
11 int main()
12 {
13     int n, m, low, high, mid, i, f;
14     int sum, x;
15     while(~scanf("%d%d", &n, &m))
16     {
17         f = 0;
18         for(i = 0; i < n; i++)
19         {
20             scanf("%d", &a[i]);
21             if(a[i] > high)
22                 high = a[i];
23         }
24         sort(a, a+n);
25         low = a[1] - a[0];
26         for(i = 2; i < n; i++)
27             if(a[i]-a[i-1] < low)
28                 low = a[i] - a[i-1];
29         while(high > low)
30         {
31             sum = 0;
32             mid = (low + high)/2;
33             x = 1;
34             for(i = 1; i < n; i++)
35             {
36                 if(a[i]-a[i-x]<mid)
37                     {
38                         sum ++;
39                         x = x+1;  //如果这个距离小于枚举的最小距离,再减的时候减去原来的点
40                     }
41                     else
42                         x = 1;
43             }
44             if(sum > m)
45                 {
46                     high = mid;
47                     f = 1;
48                 }
49             else
50                 low = mid + 1;
51         }
52         if(f)
53         printf("%d\n", high-1);
54         else
55         printf("%d\n", high);
56     }
57     return 0;
58 }