POJ3258 二分与最小值最大化

本文主要是介绍POJ3258 二分与最小值最大化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目的意思就是一排石子，拿走几个，使这些石子相邻间距中的最小值最大。不会做，只能看网上的代码，发现解释也很少，最后还是自己一点点搞懂的，但没完全搞懂，有的地方还是略不理解

这题看了网上的代码都是用二分法，那么思路是这样的，先排序，然后再从大到小假设要求的区间mid，这个区间就是一直二分得到，那么用这个区间和相邻石子的区间比较，如果小于这个区间，就把后一个石子拿走（因为前一个如果是第一个拿不走啊），并且将拿走的石子个数+1。相反就改变两两比较的前一个石子的位置，确保是两个相邻的石子比较。

如果sum大于要拿走的石子数m，说明要求的区间要小于mid，相反大于mid。这样一直改变二分的区间[left,right]，最后sum=m时，输出mid就是题解

#include<stdio.h>
#include<stdlib.h>
#include<string.h>int cmp(const void*a, const void*b)
{return *(int*)a - *(int*)b;
}int main()
{int l, n, m;int i,left,right,mid;int sum, point, step;int a[50005];while (scanf("%d%d%d", &l, &n, &m) != EOF){for (i = 1; i <= n; i++)scanf("%d", &a[i]);qsort(a + 1, n, sizeof(a[0]), cmp);a[0] = 0;a[n + 1] = l;left = 0;right = l;while (left <= right)//等于配合后面left=mid+1出循环并有的情况会相等{sum = 0;mid = (left + right) / 2;point = 0;for (i = 1; i <= n + 1; i++){//这里point的利用是考虑到如果小于，石子会被拿走，所以还是相邻间距if (a[i] - a[point] < mid) sum++;//等于的话自己也会被算入，肯定会大于m了elsepoint = i;}if (sum > m){//确保最后可以脱离循环，比如left=right循环继续，mid=right，如果不-1死循环   right = mid-1;}else   //小于等于的情况，确保相等的时候脱出{left = mid+1;//还是为了最后确保脱离循环所以+1step = mid;}}printf("%d\n", step);}
}