首页 > 代码库 > 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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。