首页 > 代码库 > nyoj-586-疯牛|poj-2456-Aggressive cows
nyoj-586-疯牛|poj-2456-Aggressive cows
http://acm.nyist.net/JudgeOnline/problem.php?pid=586
http://poj.org/problem?id=2456
解题思路:最大化最小值二分答案即可
1 #include <stdio.h>
2 #include <string.h>
3 #include <stdlib.h>
4
5 int a[100100];
6 int n, c, i;
7
8 int cmp(const void *a, const void *b){
9 return *(int *)a - *(int *)b;
10 }
11
12 bool check(int x){
13 int cnt = 1, temp = a[0];
14 for(i = 1; i < n; i++){
15 if(a[i] - temp > x){
16 cnt++;
17 temp = a[i];
18 if(cnt >= c){//如果能装下c头牛
19 return true;
20 }
21 }
22 }
23 return false;
24 }
25
26 void solve(){
27 //二分搜索最大的距离
28 int l = 0, r = a[n - 1] - a[0];
29 while(l <= r){
30 int mid = (l + r) >> 1;
31 if(check(mid)){
32 l = mid + 1;
33 }
34 else{
35 r = mid - 1;
36 }
37 }
38 printf("%d\n", l);
39 }
40 int main(){
41 while(scanf("%d %d", &n, &c) != EOF){
42 for(i = 0; i < n; i++){
43 scanf("%d", &a[i]);
44 }
45 qsort(a, n, sizeof(a[0]), cmp);
46 solve();
47 }
48 return 0;
2 #include <string.h>
3 #include <stdlib.h>
4
5 int a[100100];
6 int n, c, i;
7
8 int cmp(const void *a, const void *b){
9 return *(int *)a - *(int *)b;
10 }
11
12 bool check(int x){
13 int cnt = 1, temp = a[0];
14 for(i = 1; i < n; i++){
15 if(a[i] - temp > x){
16 cnt++;
17 temp = a[i];
18 if(cnt >= c){//如果能装下c头牛
19 return true;
20 }
21 }
22 }
23 return false;
24 }
25
26 void solve(){
27 //二分搜索最大的距离
28 int l = 0, r = a[n - 1] - a[0];
29 while(l <= r){
30 int mid = (l + r) >> 1;
31 if(check(mid)){
32 l = mid + 1;
33 }
34 else{
35 r = mid - 1;
36 }
37 }
38 printf("%d\n", l);
39 }
40 int main(){
41 while(scanf("%d %d", &n, &c) != EOF){
42 for(i = 0; i < n; i++){
43 scanf("%d", &a[i]);
44 }
45 qsort(a, n, sizeof(a[0]), cmp);
46 solve();
47 }
48 return 0;
49 }
nyoj-586-疯牛|poj-2456-Aggressive cows
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。